精华内容
下载资源
问答
  • 在对信息网络社区发现 研究的基本概念与原理进行简单介绍的 基础上,着重对各种发现方法进行分类 分析与比较. 最后,对信息网络社区发现 技术进行了总结与展望.
  • 虚拟网络社区的审计路径研究,聂小青,邱玉莲,在网络2.0时代,网络社区大量聚合。电子商务平台充斥着人们的生活,审计模式需要适应虚拟网络社区的发展,创新新的审计方案。基于
  • 鉴于网络动态变化的本质特征以及人们对社区结构准确性和实时性的要求,动态网络社区发现开始受到关注。 本文首先介绍了社区发现相关技术,分析了经典的静态和动态社区发现算法及其优缺点,例如,GN算法、KL算法、CMP算法...
  • 针对基于极大团的社区发现算法,设计了适应大规模数据的 MapReduce 并行计算框架,提出了基于大规模复杂网络社区发现的科研合著网络分析算法,并用于对我国管理科学与工程领域 2012 年科研合著网络进行社区结构划分...
  • 网络社区划分算法

    千次阅读 2018-10-12 14:10:15
    网络社区划分算法 目录  [隐藏]  1 简介 2 构建一个点击流网络 3 网络社区划分的两种主要思路:拓扑分析和流分析 4 拓扑分析 4.1 计算网络的模块化程度Q-Modularity 4.2 ...

    网络社区划分算法

    目录

      [隐藏

    简介

    使用许多互联网数据,我们都可以构建出这样的网络,其节点为某一种信息资源,如图片,视频,帖子,新闻等,连边为用户在资源之间的流动。对于这样的网络,使用社区划分算法可以揭示信息资源之间的相关性,这种相关性的发现利用了用户对信息资源的处理信息,因此比起单纯使用资源本身携带的信息来聚类(例如,使用新闻包含的关键词对新闻资源进行聚类),是一种更深刻的知识发现。

    构建一个点击流网络

    假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模,我们一般只考虑最经常被访问的一批资源。因此在数据处理中,我们考虑UV(user visit)排名前V的资源,得到节点集合|V|,然后对于一个用户i在一段时间内(例如一天)内访问的资源,选择属于|V|的子集vi。如果我们有用户访问资源的时间,就可以按照时间上的先后顺序,从vi中产生vi-1条有向边。如果我们没有时间的数据,可以vi两两间建立联系,形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低,下文中,暂时先考虑后者的情况。 对于一天内的n个用户做这个操作,最后将得到的总数为 的连边里相同的边合并,得到|M|个不同的边,每条边上都带有权重信息。这样,我们就得到了V个节点,M条边的一个加权无向网络,反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上,我们可以通过社区划分的算法对信息资源进行分类。

    网络社区划分的两种主要思路:拓扑分析和流分析

    社区划分的算法比较多,但我个人认为大致可以分为两大类:拓扑分析和流分析。前者一般适用于无向无权网络,思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络,思路是发现在网络的某种流动(物质、能量、信息)中形成的社区结构。这两种分析各有特点,具体应用取决于网络数据本身描述的对象和研究者想要获得的信息。


    Community figure 1.png

     

    我们可以将已知的一些算法归入这两类:

    算法 优化目标 计算复杂度 适用情况 局限
    拓扑分析        
    Q Modularity 最大化Q-modularity V|^2 无向无权多分量 不适用小网络
    Edge-Betweenness 最小化社区间连边的betweenness V|*|E|^2 有向有权多分量
    Leading Eigenvector 对拉普拉斯矩阵第二小特征根对应的特征向量聚类 V|^2+ |E| 无向无权多分量  
    Fast Greedy 使用社区合并算法来快速搜索最大Q-modularity E|*log(|V|) 无向有权多分量 不适用小网络
    Multi Level 使用社区展开算法来快速搜索最大Q-modularity V| 无向有权多分量 不适用小网络
    流分析        
    Walk Trap 最大化社区间的流距离 E|*|V|^2 无向有权单分量  
    Label Propagation 每个节点取邻居中最流行的标签,迭代式收敛 V| + |E| 无向有权单分量 结果不稳定
    Info map 最小化随机流的编码长度 V|*(|V|+|E|) 有向有权单分量  
    Role-based community 划分出在流中地位类似的节点 V|^3 有向有权单分量 结果不稳定

     

    上表中的分量(component)指在网络中的独立“团块”。有向网络里,分量有强弱之分,强分量(strong component )中任意一个节点都可到达另外一个节点,弱分量(weak component)中如果忽略连边方向,则构成强分量。无向网里分量没有强弱之分。在网络中识别强分量的算法有Kosaraju算法,Tarjan算法及其变形Gabow算法等。在这里不展开叙述。 接下来,我们逐一讨论拓扑分析和流分析中的各种算法的具体思路。

    拓扑分析

    计算网络的模块化程度Q-Modularity

    Q-Modularity是一个定义在[-0.5,1)区间内的指标,其算法是对于某一种社区结构,考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望,说明节点越有集中在某些社区内的趋势,即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估,但因为这个指标科学合理,而且弥补了这个方面的空白,迅速成为一般性的社区划分算法的通用标准。 Q的具体计算公式如下: Community figure 2.png

    其中A是网络G对应的邻接矩阵,如果从i到j存在边,则Aij=1,否则为0。m是总连接数,2m是总度数,Aij/2m是两节点之间连接的实际概率。Ki和kj分别是i和j的度数。如果我们保持一个网络的度分布但对其连边进行随机洗牌,任意一对节点在洗牌后存在连接的概率为kikj/(2m)2。上式中中括号表达的就是节点之间的实际连边概率高于期待值的程度。后面跟着一个二元函数,如果节点ij属于同一个社区,则为1,否则为0,这就保证了我们只考虑社区内部的连边。刚才这个定义是以节点为分析单位。实际上,如果以社区为分析单位看Q指标,可以进一步将其化简为eii和ai之间的差。其中eii是在第i个社区内部的link占网络总link的比例,ai是第i个社区和所有其他社区的社区间link数。

    上式已经清楚定义了Q,但在实际计算里,上式要求对社区及其内部节点进行遍历,这个计算复杂度是很大的。Newman(2006)对上式进行了化简,得到矩阵表达如下: 我们定义Sir为n * r的矩阵,n是节点数,r是社区数。如果节点i属于社区r,则为1,否则为0。则有Community figure 3.png

    于是有

    Community figure 4.png

    其中B是modularity matrix,其元素为

    Community figure 5.png

    该矩阵的行列和都是0,因为实际网络和随机洗牌后的网络度分布是不变的。特别地,在仅仅有两个社区的情况下(r=2),可以s定义为一个n长的向量,节点属于一个社区为1,属于另一个社区为-1,Q可以写成一个更简单的形式:

    Community figure 6.png

    通过对社区的划分可能空间进行搜索,可以得到最大化Q值的社区划分。在这个过程会涉及数值优化的部分,例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman(2006),它通过不断合并社区来观察Q的增加趋势,得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) ),在最好的情况下接近线性复杂度的算法。

    计算网络的连边紧密度Edge betweenness

    这个思路出现得比较早(Newman, 2001)。Freeman (1975) 提出过一个叫betweenness的指标,它衡量的是网络里一个节点占据其他n-1节点间捷径的程度。具体而言,首先对每一对节点寻找最短路径,得到一个n * (n-1)/2的最短路径集合S,然后看这个集合中有多少最短路径需要通过某个具体的节点。Newman借鉴了这个标准,但不是用来分析节点而是分析连边。一个连边的edge betweenness就是S集合里的最短路径包含该连边的个数。 定义了连边的betweenness后,就可以通过迭代算法来进行社区划分了。具体做法是先计算所有连边的betweenness,然后去除最高值连边,再重新计算,再去除最高值连边,如此反复,直到网络中的所有连边都被移除。在这个过程中网络就逐渐被切成一个个越来越小的component。在这个过程中,我们同样可以用Q-modularity来衡量社区划分的结果。这种算法定义比较清晰,也不涉及矩阵数学等运算,但问题是计算复杂度比较大。

    计算网络拉普拉斯矩阵的特征向量Leading eigenvector

    一个有n个节点的网络G可以被表达为一个n x n的邻接矩阵(adjacency matrix)A。在这个矩阵上,如果节点i和j之间存在连边,则Aij=1,否则为0。当网络是无向的时候,Aij=Aji。另外我们可以构造n x n的度矩阵(degree matrix)D。D对角线上的元素即节点度数,例如Dii为节点i的度数,所有非对角线的元素都是0。无向网的分析不存在度数的选择问题,有向网则要根据分析目标考虑使用出度还是入度。将度数矩阵减去邻接矩阵即得到拉普拉斯矩阵,即L = D-A。

    L的特征根\lambda_0 <= \lambda_1 <= ...<= \lambda_{n-1}存在一些有趣性质。首先,最小的特征根总等于0。因为如果将L乘以一个有n个元素的单位向量,相当于计算每一行的和,刚好是节点的度的自我抵消,结果等于0。其次,特征根中0 的个数即无向网G中分量的个数。这意味着如果除了最小特征根,没有别的特征根为0,则整个网络构成一个整体。

    在这些特征根里,第二小的特征根(或者最小的非零特征根)\lambda_1又叫做代数连通性(algebraic connectivity),其对应的特征向量叫做Fidler vector。当\lambda_1 >0,说明网络是一个整体。\lambda_1越大,说明网络彼此间的链接越紧密。从这个定义来看,非常像前面讨论的Q-Modularity,实际上在Newman2006的文章里,确实讨论了二者在数学上的对应关系。例如对示例网络所对应的进行分析,可以得到拉普拉斯矩阵如下:

    Community figure 7.png


    这个矩阵的特征根如下:{5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0}。取\lambda_1 =1时, Fidler vector={0.29, 0.00, 0.29, 0.29, 0.29, -0.58, -0.58, 0.00}。因为Fidler vector的值分别对应着图里的节点,于是可以写成{a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00}。仅仅从元素的正负号就可以看出,该分析建议我们把f和g节点与其他节点分开,更细致的,对元素值大小的考察则建议把矩阵分成三个社区,{{a, c, d, e}, {b, h}, {e, f}}。回到图中考察,我们发现这个社区分类基本是合理的。

    通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值

    通过multi level方法搜索网络模块化程度Q-Modularity的最大值

    因为以上两种方法都是基于Q-modularity的,只不过是搜索策略的不同,所以在此不展开讨论。

    流分析

    随机游走算法Walk Trap

    P. Pons 和 M. Latapy 2005年提出了一个基于随机游走的网络社区划分算法。他们提出可以使用两点到第三点的流距离之差来衡量两点之间的相似性,从而为划分社区服务。其具体过程如下:首先对网络G所对应的邻接矩阵A按行归一化,得到概率转移矩阵(transition matrix)P。使用矩阵计算表达这个归一化过程,可以写作

    Community figure 8.png

    其中A是邻接矩阵,D是度矩阵。利用P矩阵的马可夫性质可知,它的t次方的元素Pijt就代表着随机游走的粒子经过t步从节点i到j的概率。其次,定义两点ij间的距离如下:

    Community figure 9.png

    其中t是流的步长。步长必须恰当选择,因为如果t太小,不足以体现网络的结构特征,如果t太大,则Pijt趋近于与j的度数d(j)成正比, 随机游出发点i的拓扑信息被抹去。作者建议的t经验值为3到5之间。k是某一个目标节点。所以这个公式描述的是经过t步,ij到目标节点k的平均流转移概率(因为这个概率与中间节点k的度数d(k)成正比,所以要除以d(k)来去除这个影响)。ij到网络所有其他点之间的距离差别越小,说明ij很可能位于及其类似的位置上,彼此之间的距离也越接近。值得注意的是,这个思路如果只考虑一个或少数的目标节点,是不合适的。因为rij实际上只是结构对称性。有可能ij在网络的两端,距离很远,但到中间某个节点的距离是相等的。但因为公式要求k要遍历网络中除了ij以外的所有节点,这个时候ij如果到所有其他节点的流距离都差不多,比较可能是ij本身就是邻居,而不仅仅是结构上的对称。如公式所示,rij表达可以写成矩阵表达,其中Pti•是第P的t次方后第i行。

    定义了任意两点之间的距离rij后,就可以将其推广,得到社区之间的距离rc1c2了:

    Community figure 10.png

    容易看出,这个距离与节点之间的距离很相似,只不过这次是计算两个社区分别到目标节点k的流距离,而计算单个社区C到节点k的流距离时,又是对社区C内所有节点到k流距离取平均。

    一旦从流结构中提取了节点相似性,社区划分就是一个比较简单的聚类问题。例如可以采取合并式聚类法如下:先将每个节点视为一个社区,然后计算所有存在连边的社区之间的流距离。然后,取两个彼此连接且流距离最短社区进行合并,重新计算社区之间的距离,如此不断迭代,直到所有的节点都被放入同一个社区。这个过程社区的数目不断减小,导致出现一个树图分层(dendrogram)结构。在这个过程中,可以使用Q-modularity的变化来指导搜索的方向。

    标签扩散算法label propagation

    这种算法的思路源于冯诺依曼在50年代提出的元胞自动机模型(cellular automata)和Bak等人在2002年左右做的沙堆模型。该算法的基本原理如下:首先,给全网每个节点分配一个不重复的标签(label);其次,在迭代的每一步,让一个节点采用在它所有的邻居节点中最流行的标签(如果最佳候选标签超过一个,则在其中随机抽一个),;最后,在迭代收敛时,采用同一种标签的节点被归入同一个社区。 这个算法的核心是通过标签的扩散来模拟某种流在网络上的扩散。其优势是算法简单,特别适用于分析被流所塑造的网络。在大多数情况下可以快速收敛。其缺陷是,迭代的结果有可能不稳定,尤其在不考虑连边的权重时,如果社区结构不明显,或者网络比较小时,有可能所有的节点都被归入同一个社区。

    流编码算法 the Map Equation

    Rosvall和Axelsson 2009年提出了一种很有意思的方法来研究网络中的流动。其核心思想是,好的社区划分要令网络上流的平均描述长度最短。他们认为,分析有向加权网络的一个好的视角是观察某类实体(货币、能量、信息)在网络上的流动。即使没有实体流动的数据,我们也可以根据网络的基本结构来推测随机游走的粒子的轨迹,然后对得到的“平均流”进行信息编码。对“平均流”的描述长度最短的编码机制,就对应着对社区的一种最有效划分。

    首先要讨论的是节点层编码。最简单的方式是给每个节点分配一个独特的二进制签名。但这种编码方式并不高效,因为节点被访问的概率并不一样。为了改进,我们可以引入一个Huffman编码表(code book),在这个编码表上,每个节点都对应一个独立的二进制编码,但码长与节点被访问的概率(通过转移矩阵P在无穷步后的收敛结果来计算)相反。这样,“平均流”的信息长度就大大被降低了。 其次,我们还可以通过引入两层编码,节点编码和社区编码,来进一步降低信息长度。有了社区编码的好处是,两个或多个社区内部的节点编码是可以重复的,这就进一步降低了信息长度。需要注意的是,两层编码并不意味着像国际电话区号那样,在每个节点前加一个社区前缀码,因为这样的话其实就和单层编码没有什么区别了。这里的两层编码实际上是在利用流的“局域性”。只需要我们标识出社区的入口(即社区编码)和出口(定义在社区间连边上的编码),在此区域内访问的节点,可以直接使用节点层的编码,不用考虑社区编码。例如:11-0000-11-01-101-100-101-01-0001-0-110-011-00-110-00-111-… 在这个流中,加粗的0前面,节点都在一个社区里游走,所以直接使用节点编码,0001是一个社区出口连边(exit)编码,使用了这个编码意味着节点要跳转社区,接下来0这个社区编码被使用,意味着流进入0社区,在这里面再次直接使用节点编码,直到跳出0社区(0社区的exit被使用)。

    在这个两层编码体系中,包括三类码表(code book)。第一个是主码表(master code book),决定每个社区的编码;第二个是传送门码表(exit code book),决定每个社区的出口连边的编码;第三个是节点码表(node code book),决定每个社区内的节点的编码。一旦对网络的社区划分P(partition)给定,就存在一个社区码表,一个传送门码表,和m个节点码表,其中m是社区的个数。最后,社区划分的目标就是要最小化所有码表的总长,或者按论文中的说法,平均随机游走中的一步所耗费的信息成本。 这个思路以一种很有趣的方式利用了网络社区的定义。网络社区的存在,意味着社区内的流动较多,跨越社区的流动较少。因此,一个好的社区划分意味着主码表和传送门码表被调用的次数都很少,描述的信息配额(quota)主要用于描述社区内的流动。相反,如果待分析的是一个随机的网络,或者研究者构造了一种低效的社区划分,那么主码表和传送门码表被调用的次数将会很多。特别是传送门码表,也就是错误的社区划分会大大加大这个码长。

    一个总结了以上思想的公式可以表达如下,作者称之为the map equation。

    Community figure 11.png

    其中M即对网络的某种社区划分得到m个社区。L是该划分所对应的信息描述长度。qi->代表进出第i个社区的概率(先考虑无向网络),因此q->代表社区间跳转的总概率。H(Q)是社区间跳转行为的香农信息量。Pi->代表第i个社区内节点间跳转的总概率,H(Pi)是第i个社区内节点间跳转行为的香农信息量。在公式的两个部分,信息量都用其被使用的频率进行加权。经过展开化简,可以得到简化形式如下:

    Community figure 12.png

    最后,使用某种社区划分的搜索策略(主要有细分与合并两种)来寻找该描述长度的最小值即可。值得注意的是,在实际计算中,节点层的信息量(第三项)是不需要考虑的。

    流层级算法 Role-based Similarity

    Cooper和Barahona 在2010年提出了一个算法,可以揭示网络中流的层级关系。他们认为,通过对网络的邻接矩阵A进行分析,可以得到一个节点从一步到k步的出流或入流的画像(flow profile),在任意两个节点之间比较这种流画像,就可以得到节点之间的相似性,从而为社区划分服务。

    具体过程如下:先得到网络的邻接矩阵A,这个时候V=AKI中的元素Vi就代表第i个节点在k步的所有出流之和。类似地,U=(AT)KI中的元素Ui就代表第i个节点在k步的入流之和。

    Community figure 13.png

    如公式所示,我们可以构造n * k的矩阵Xin,其元素Xinij代表第i个节点在第k步的入流;也可以构造Xout,其元素Xoutij代表第i个节点在第k步的出流。把Xin和Xout横着拼在一起,就是X。其维度为n * 2k。在X矩阵上,第i行正好描述了节点i在k步内的所有入流和出流的信息。因此,可以通过计算第i行和j行的Cosine距离或者Manhattan距离等来定义节点相关性rij,最后得到的相关性矩阵,就可以用于聚类。

    Community figure 14.png

    图3展示了将role-based similarity方法用于分析一个示例流网络的结果。发现分类的结果确实反映了流的层级关系。值得注意的是,虽然在论文中作者建议使用Cosine距离,但我发现在这个实例网络上,使用Manhattan距离的结果能更清晰地揭示流层级结构。因此,具体的分析要看数据的情况,这也是应用这种算法需要考虑的局限之一。

    总结

    Community figure 15.png


    本文中我们总结了构建点击流网络之后,使用社区划分算法来对点进行聚类的不同思路。主要可以分为拓扑分析和流分析两种,从数学角度看,前者以频谱分析(Spectral analysis)为主要手段,后者以马可夫链(Markov chain)为主要建模工具。其中流编码算法较为独特,以信息论为主要工具。但值得注意的是,由于编码算法仍然是在处理流,所以本质上只是对马可夫链的一种处理。例如在图4中,编码算法没有能区分开节点,而是将所有的节点归为一个区,每个节点被访问的流概率恰好等于其Page rank值(与节点的大小和颜色深度成正比)。而我们知道Page rank也仍然是基于马可夫链的。这个时候平均每走一步要消耗2.71比特信息。

    展开全文
  • 问答式网络社区营销

    2020-12-05 19:28:16
    问答式网络社区(ASK)的概念 问答式网络社区是一种知识问答式网络社区,具体包括:百度知道,腾讯问答,新浪爱问,知乎网站等。在这些网站里,用户可以提出问题,也可以回答别人提出的问题。从而企业可以获得利用...

    问答式网络社区(ASK)的概念
    问答式网络社区是一种知识问答式网络社区,具体包括:百度知道腾讯问答新浪爱问知乎网站等。在这些网站里,用户可以提出问题,也可以回答别人提出的问题。从而企业可以获得利用问答进行网络推广的机会。

    问答式网络社区(ASK)的价值

    • ASK网络社区在网络营销中的作用
    1. 形成信任和口碑效应
    2. 提高企业信息化网络可见度
    • 百度知道在网络营销中的作用
    1. 百度知道中的数据可以反映到搜索结果中
    2. 能精准找到目标客户
    3. 易提高品牌知名度和信誉度

    问答式网络社区(ASK)的要点

    1. 做ASK社区有价值的活跃用户
      每次问答都是品牌展示的机会
      有利于在业内建立知名度和可信度
    2. 从专业角度选择问题及提供解决方法
      更易获得用户的认可
    3. 扩大ASK社区信息的传播范围
      更多展示的机会
    展开全文
  • 随着人们生产生活信息化的深入,信息网络的社区发现研究引起...在对信息网络社区发现研究的基本概念与原理进行简单介绍的基础上,着重对各种发现方法进行分类分析与比较.最后,对信息网络社区发现技术进行了总结与展望.
  • 复杂网络社区挖掘综述,介绍社交网络重叠和非重叠社区的挖掘
  • 基于大规模复杂网络社区发现的科研合著网络分析,武森,卢丹,针对基于极大团的社区发现算法,设计适应大规模数据的MapReduce并行计算框架,提出基于大规模复杂网络社区发现的科研合著网络分析算
  • 提出一种基于网络社区发现的低随机性标签传播聚类算法. 首先, 用半径和最近邻方法将数据集构建为稀疏的全连通网络. 之后, 根据节点相似度进行节点标签预处理, 使得相似的节点具有相同的标签. 用节点的影响力值改进...
  • 随后结合实例介绍了异质网络社区发现的现有研究方法,包括基于主题模型、基于排序和聚类相结合、基于数据重构和基于降维的方法等,并针对各类方法指出了其特点和局限性;最后讨论了当前该领域在结构复杂性、建模复杂...
  • 由于二分网络特殊的二分结构,使得基于单模网络的现有社区发现算法无法适用。...在人工网络和真实网络上的实验和分析表明,该算法能够有效挖掘二分网络社区结构,改善二分网络社区发现的准确性和效率。
  • 分析了基于优化模块度检测复杂网络社区结构的算法存在解的限制问题,即不能检测出小于一定内在尺度的社区,并提出了基于极值优化模块密度来检测复杂网络社区结构的启发式算法,通过调整局部极值来优化全局的变量,使算法...
  • 社会网络社区的发展

    2011-12-22 10:14:18
    资源介绍了社会网络社区的发展以及调查研究报告,
  • 问答式网络社区(ASK) 一、问答式网络社区(ASK)的概念 问答式网络社区是一种知识问答式网络社区,如百度知道、腾讯问间、新浪爱问、知乎网站等。在这些ASK社区中,用户可以提出问题,同时每一个人也都可以去回答...

    问答式网络社区(ASK)

    一、问答式网络社区(ASK)的概念
    问答式网络社区是一种知识问答式网络社区,如百度知道、腾讯问间、新浪爱问、知乎网站等。在这些ASK社区中,用户可以提出问题,同时每一个人也都可以去回答别人的问题,正是这种“问答”,为一些企业的“网络推广”带来了机会。
    在这里插入图片描述
    二、问答式网络社区(ASK)的价值
    1.ASK网络社区在网络营销中的作用利用ASK网络社区开展网络营销的作用主要体现在两个方面:
    第一,ASK网络社区庞大的用户群体互动交流,通过解答用户提出的实际问题而形成信任和口碑效应,因而对于网络品牌和网络推广具有一定的效果。
    第二,利用第三方ASK平台良好的搜索引擎友好性提高企业信息网络可见度,例如通过一些关键词搜索时,搜索结果中通常可以看到“百度知道”相关内容。

    2.百度知道在网络营销中的作用
    当前最受欢迎的问答平台有百度知道和腾讯问问,因其人气旺、分类明细清楚、内容更新快、有完善的奖励机制,很贴近网民的需要。如果企业能巧妙地利用问答推广,就会很容易找到目标客户,提高品牌知名度和信誉度。以百度知道为例,最大的特点在于和搜索引擎完美结合。百度知道的作用可以表述为:
    第一,百度知道中的数据可以反映到搜索结果中,用户只要在百度中搜索问题,百度知道就会提供相应问题的答案。
    第二,能精准找到目标客户,百度知道中的问题都需要贴标签,有了这些标签用户可以快捷地找到答案,推广者可以精准地找到目标客户。
    第三,百度知道呈现的是用户互相之间回答和互助的一种模式,这能很好地拉近人与人之间的距离以及信任度,企业在问答平台上做推广,更容易提高品牌知名度和信誉度。

    三、ASK网络社区营销的要点
    问答式网络社区网络营销的要点可归纳为三个方面:
    1.从专业的角度选择问题及提供解决方法由于ASK网络社区中用户提问和回答问题有较大的随意性,有些提问可能不够专业,有些回答可能不够完善,因此,以专业和严谨的态度解决用户提出的新问题或是自己提出引导性问题并回复,更容易获得用户的认可。专业,也是利用ASK网络社区开展网络营销的基础。
    2.做ASK社区有价值的活跃用户做一个活跃用户,经常关注用户提出的问题,持续为用户提供有价值的解答,同时也可以将自己发现的问题提出来与他人一起探讨,如同专业博客和微博一样,是在行内建立知名度及可信度的途径之一,尤其以企业或者品牌名称作为用户ID,每次问答都是品牌展示的机会。
    3.扩大ASK社区信息的传播范围
    与微博信息推广一样,一些用户关心的问题除了在ASK平台内部传播之外,还可以在其他平台继续传播。例如,将有关问题及解答作为企业网站FAQ或者博客的内容发布;当然也可以针对某些重要问题及解答页面进行必要的搜索引擎优化处理,从而增加公共搜索引擎结果展示的机会。

    展开全文
  • 网络社区数据的可信存储验证技术,李卓然,吴旭,随着信息技术的发展,网络社区数据的可信性也受到了严峻的考验。为使网络社区数据在各个系统之间更快、更安全地得以使用、交换和
  • 复杂网络社区划分方法综述

    千次阅读 2019-03-13 17:42:58
    摘 要:复杂网络在现实网络表现为多种形式,本文将从2002年以来经典社区划分方法入手,对复杂网络社区划分的研究现状进行一个综合简单的描述和概括,试图为社区划分研究描绘出一个较为全面和清晰的轮廓,为该领域的...

    [转] https://blog.csdn.net/u012369559/article/details/79210117

    摘 要:复杂网络在现实网络表现为多种形式,本文将从2002年以来经典社区划分方法入手,对复杂网络社区划分的研究现状进行一个综合简单的描述和概括,试图为社区划分研究描绘出一个较为全面和清晰的轮廓,为该领域的后续研究提供有益的参照。 
      关键词:复杂网络;社区划分;形式;综述 
      中图分类号:TU984.12 文献标识码:A 文章编号:1674-7712 (2014) 12-0000-02 
      复杂网络在现实网络表现为多种形式,如社会系统中的科学合作网、人际关系网,生物系统中的基因调控网、蛋白质大分子之间交互网和流行病传播网、蛋白质交互网,科技系统中的电话网、因特网和万维网等等。同时,复杂网络更加普遍存在一些统计特征,如表达复杂网络中节点服从幂律分布特征的“无标度特性”,反映网络短路径长度和高聚类系数特点的“小世界效应”和反映网络中普遍在的同一社区中节点连接紧密、不同社区节点连接稀疏特征的“社区结构”等等 。一般认为社区结构(簇)是指复杂网络中由具有相同或相似属性构成的社区,不同的社区结构在特定的网络中具有不同的性质和特征,如:人际关系网络中由相同的兴趣而形成的人群,蛋白质网络中具有相似功能的蛋白质群等。 
      自从2002年,Girvan和Newman提出著名的社区挖掘GN(Girvan-Newman)算法[1],此后很多复杂网络社区挖掘方法相继被提出,在新的理论、方法层出不穷,新的应用领域也不断涌现的背景下。如何发现复杂网络中的社区结构,已经成为最具挑战的多学科交叉研究课题之一,吸引了来自生物、社会、物理、计算机、数学等多领域的研究者。 
      本文将从2002年以来经典社区划分方法入手,对复杂网络社区划分的研究现状进行一个综合简单的描述和概括,本文试图为社区划分研究描绘出一个较为全面和清晰的轮廓,为该领域的后续研究提供有益的参照。 
      一、社区挖掘方法 
      (一)基于模块度的社区划分 
      2002年,Girvan和Newman基于启发式规则提出著名的社区挖GN(Girvan-Newman)算法[1],该算法从社区间的连接边介数入手,根据社区间边介数应大于社区内部链接的边介数,通过反复计算边介数,移除边介数最大的边,自顶向下的方式建立一颗层次聚类树的方法来划分社区。其中边介数定义为:网络中经过每条边的最短路径的数目。通过在实际网络中的应用发现该方法的划分的结果精度高,但是计算速度较慢;对于一个具有m条边,n个节点的网络时间复杂度为O(mn2),并且该算法没有对于社区在什么时候进行划分提出一个有效的方法。 
      2003年,Tyler等人将采用蒙特卡洛方法[3]引入GN算法中,引入统计方法来估算其中部分节点的链接的近似边介数,提出了一种近似的Gn算法,由于其实计算部分网络而不是全部网络,因此,该算法是以牺牲精度为代价来提高计算的精度。 
      2004年,Girvan和Newman针对GN算法中无衡量社区划分标准的不足,引入的函数Q值模块度计算。将次改进算法运用到了实际网络跆拳道网络中得到了很好的划分结果。该模块度定义为以后社区划分的优劣提供了一个衡量的标准。该算法的缺点是算法的复杂度和之前相比并没有什么改进。 
      于是同年,Newman又提出了基于模块性优化的快速社区发现算法(FN算法[2]),该算法的过程和GN算法恰好相反,算法采用自底向上的层次聚类过程构成一颗层次聚类树,在合并的过程中引入DQ,每次合并选择使函数Q值增大最大或者减小最小的方向进行社区的合并操作,当最终社区合并为一个社区时,只要在对应Q值最大处断开即可得到聚类的结果。通过对实际网络划分的应用,对于一个m条边,n个节点的网络,该算法的复杂度为O(mn+n2)。算法的时间复杂度得到了很大的改善。但是算法也具有很大缺陷,在于其求解是局部最优解,精度相较于GN算法低。虽然其后Newman、Clauster等人继续对FN算法进行了优化,利用堆栈结构队,提出了一种新的贪婪算法CNM算法。该算法的复杂度O(nlog2n),已经接近于线性复杂度,但是算法的局部最优解问题依旧没有得到改善。 
      2005年,Guimera和Amaral基于退火算法原理,提出了退火模块性优化算法(SA)[3]。该算法的设计思想是在计算之前要给一个初始社区划分,这个初始的社区划分可以任意的,在初始社区的基础上通过迭代不断产生新的社区解,在迭代过程中同时计算相应Q值。SA算法不同与GN算法和FN算法的,SA算法在计算新的候选解时是将节点划分到其他社区、通过社区之间交换节点,再次分解社区或者合并社区。并且该算法中应用了模拟退火策略的Metropolis准则来判断该社区结果是否是当前的最优解。SA算法在实际的数据集上应用的结果中得到了十分好的结果,不足之处是每次迭代都要产生很多的候选结果,因此该算法的时间复杂度较高,运行效率较低。 
      2006年,Newman基于模块度函数Q值,提出了优化函数Q的谱方法[4]。Newman通过引入谱图理论研究模块度优化。用图拉普拉斯矩阵来表示模块度函数Q,该矩阵又称为模块性矩阵;并证明了这个矩阵的第二大特征值的特征向量的正负二分结果,正好对应了模块性优化的二分结果;通过在实际网络上的应用,该算法的聚类结果接近实际网络,但其时间复杂度仍较高,介于O(n2 log n)和O(n log n)之间。 
      2007年,杨博、Cheng和Liu等人[3]通过基于马尔科夫随机游走模型提出了网络聚类算法算法(FEC算法)。该算法的假设是:开始从任意社区开始随机游走,根据在整个网络中的随机游走到达该起始社区内节点的期望值,应大于到达起始社区外节点的期望值的思想。算法采用了启发策略,综合了两种分簇标准(连接密度和连接符号)的复杂网络社区发现聚类算法,理论上该算法既能很好的处理符号网络,又能较精确的处理仅包含“正关系”的一般复杂网络,对于噪声高和网络社区结构明显的网络社区划分的结果也相当精确。实验结果表明FEC算法在时间和精度方面有很好的性能。但是由于该算法需要采用随机游走的步长作为参数,而对于这个步长参数,目前还没有一个能够有效针对不同网络设置最优参数的方法,所以对于步长的设置最终会直接影响最终的聚类结果的精度,一般认为对于步长的取值在[6,20]之间较为合适。   2009年,Barber等人将算法LPA[4]转化为一个函数优化问题,给出了目标函数。通过讨论与研究该目标函数的特性,来进行社区的划分,LPA在原理及实际应用方面的缺陷,需要注意,表示社区划分质量的提高并不和目标函数值的增加相一致。因此,他们对目标函数进行了相应的改进,给出一个带约束的标签传播LPAm算法。该算法的目标函数恰好是模块度函数Q值,因此,改进后的算法对应了模块性函数优化,解决了在文献[2]中所提出的问题。 
      2011年,刘大有等人[3]从局部观点出发,根据复杂网络的规模不断变大、且某些特性呈天然分布式特性的特点。并且针对单个节点社区划分的归属,利用局部目标函数f,对模块度函数Q进行了分析,提出了一种快速的社区挖掘算法(FNCA算法)。该算法证明了模块度函数Q值会伴随着网络中任意节点的函数f的单调递增,Q值呈现出单调递增特性;在此理论的基础上提出基于局部优化的近似线性的社区挖掘算法。在算法中,每个节点只利用网络局部社区结构信息优化自身的目标函数f,通过节点之间的相互协同实现整个网络的聚类过程,该算法能用于分布式网络社区挖掘,又能用于分布式网络社区网络挖掘,通过对实际网络社区划分的结果分析,该算法的时间复杂度较低,精度较高。 
      (二)基于节点相似性的社区划分 
      2006年Leicht,Holme P,Newman等人提出的LHN算法[7],该算利用网络邻接矩阵A来定义矩阵SLHN=2lamtD-1(I-QA/lamt),其中任意一个元素代表两个节点之间的相似度大小,lamt是邻接矩阵A的最大特征值,D是由节点连接数组成的对焦矩阵,QA是一个介于[0,1]之间的参数,以保证矩阵逆的存在,该算法根据随机游走理论,定义节点Vi和Vj间的平均通勤时间定义为:2m(lii+ljj-2lij),其中还lij表示矩阵L=(D-A)+的相应元素,该算法具有很高的计算复杂度,不适合大型网络计算。 
      2007年,Frey和Dueck通过3个迭代公式不断的对两个消息R和A进行更新,提出了近邻传播算法AP算法[6],该算法又被称为基于消息传递的聚类算法。AP算法的思想是将网络中每个点都作为聚类中心节点,然后计算中心节点与其他节点的相互吸引信息R(i,k)和归属信息A(i,k),前者称为点k对点i的吸引度,用来描述数据点k适用于作为数据点i的类社区代表程度,后者代表点i对点k的归属度,用来描述数据点i选择数据点k作为其类代表的适合程度,当二者之和越大,点k作为最终聚类中心节点的可能性就越大。该算法在实际的网络中应用显示精度比K-means算法结果精度要好,时间复杂度为O(n2)。 
      2010年,AHn[6]等人基于边的思想划分链接的层次聚类社区划分的方法。该算法的思想是:给定由节点k连接的一对边eik和ejk,用jaccard指数来计算节点i和j之间的相似度S(eik,ejk),S(eik,ejk)=|n+(i) n+(j)|/|n+(i) n+(j)|,其中n+(i)为包含节点i及其邻居节点的集合,n+(j)为包含节点j及其邻居节点的集合。而后通过利用单链层次聚类方法,逐层的向上产生一棵连接社区的层次树。最后定义一个用于划分该层次树的密度函数D,在相应位置断开来获得最优链接划分。通过该算法在实际网络划分中的应用,该算法的时间复杂度为O(nk2),其中kmax是网络中最大的节点的度数。 
      2011年,姜雅文等人针对GN算法的不足,提出一种基于节点相似度的节点分裂算法SCN[5],该算法通过计算顶点间的相似度而非GN算法中的边介数,针降低了算法时间复杂度。相比传统算法的节点相似性计算和GN算法,在速度和精度上都有较为明显的改善。该算法的时间复杂度介于O(n2)和O(n3)之间。 
      2011年,刘大有[5]等人提出基于集成网络重叠社区挖掘算法(UEOC),该算法将原始网络同对应的退火网络转换成一个集成网络,针对集成网络给出的Maekov游走方法,逐渐找出网络社区,然后通过引入局部社区函数“导电率”,又被成为相似性函数;通过该函数作为社区划分的标准,将已经找到的社区全部被抽取出来,通过在实际网络中的应用发现该算法不但适合于普通网络,而且适合于重叠网络,且算法只需要一个无需先验知识就能很容易被确定的参数。该算法的时间复杂度为O(Kn2),其中n 为网络中节点的个数K为重叠社区个数。 
      二、结束语 
      本文主要是从两个方面对现有的工作进行了综述:(1)根据所采用的原理从模块度与相似性两个角度进行分类,并从中选择了典型的算法进行介绍;(2)从算法辨识的精度和时间复杂度两个方面进行定量分析、比较了一些典型方法的性能。 
      社区划分的方法基本上都是在以上两种思想的基础上进行的,虽然社区划分算法层出不穷,取得了很多让人兴奋的结果,但是社区划分中依旧还有很多的问题没有得到解决: 
      第一,关于社区的定义,现在大家公认的是Newman的模块度定义,但是基于相似性、基于反社区的思想在实际应用中也取得了比较好的结果,加上对于现实网络的高度复杂性,网络中节点和边的属性等因素很少被考虑到社区划分中,因此,现在很多各具特色的观点,都尚难以达成共识,人们难以判断一个方法的好坏,也无法控制大量新方法的产生。 
      第二,关于重叠网络、层次网络、二分网络的划分,目前对于既能发现重叠网络,又能发现层次网络的算法并不多见,并且大多数的都是在单部图上面对网络进行划分;大量的算法在社区划分中既没有考虑到网络本身所具有的各种属性,也没有考虑到网络所具有的结构特征,因此,对于重叠网络、层次网络、二分网络的划分的研究将会继续是一个热点。 
      参考文献: 
      [1]Clauset A,Newman M E J,Moore C.Finding community structure in very large network,Phys.Rev.E,2004(70):066111. 
      [2]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006(09). 
      [3]刘大有,金弟,何东晓.复杂网络社区挖掘综述[J].计算机研究与发展,2012(09). 
      [4]Santo Fortunato.Community detection in graphs,fortunato@isi.it,2012(11). 
      [5]阳广元,曹霞.国内社区发现研究进展[J].情报资料工作,2014(02). 
      [6]Cheng SQ,Shen HW,Zhang GQ,Cheng XQ.Survey of signed network research.Ruan Jian Xue Bao/Journal of Software,2014(01):1?15(in Chinese). 
      [7]金弟,杨博.复杂网络簇结构探测――基于随机游走的蚁群算法[J].软件学报,2012(03):451-164. 
      [作者简介]顾跃举,男,辽宁辽阳人,武警辽宁省总队网管中心助理工程师,研究方向:计算机系统应用于维护。

    展开全文
  • 复杂网络社区发现方法 收藏来自:http://photo.blog.sina.com.cn/list/blogpic.php?pid=63891e61xc79aaca627b6&bid=63891e610101722t&uid=1669930593 转载于:...
  • 基于加权标签扩散的复杂网络社区发现算法的研究,寻找复杂的网络社区,给顶点和边加权计算。
  • SNS社交网络社区网站设计 系统设计 数据库设计 毕业论文
  • 基于复杂网络社区划分的网络拓扑结构可视化布局算法
  • 基于共享局部结构的异构网络社区发现,王培英,朱振峰,社区挖掘作为社会网络分析领域的一个热点,近几年得到广泛而深入的研究。目前关于社区发现的大多数算法都是假定网络节点间只存在��
  • 动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,提出了一种基于联合矩阵分解的动态异质网络...
  • 一种基于层次聚类的复杂网络社区划分算法,朱帅兵,殷传涛,随着互联网的发展和普及,人们对复杂网络的研究越来越多。复杂网络中存在社区结构,而找出社区结构有助于挖掘复杂网络中一些有用
  • 基于学术社团中心度的合著网络社区发现算法,吴渝,常雨箫,针对现有合著网络社区划分算法对合著网络特性体现不充分的问题,提出一种新的基于学术社团中心度的社区划分算法。该算法提出了考
  • 【软件名称】云域社区 【功能介绍】资源分享,游戏交流交友 【下载地址】http://sss.shmmec.com/apk.apk 图片

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,682
精华内容 6,672
关键字:

网络社区