社团结构

来自集智百科
跳转到: 导航搜索

引言 在复杂网络的研究中,如果能很容易的将网络中的节点划分为多个(可能会重叠的)集合,使得集合内的点相互之间稠密连接,那么就称这个网络具有社团结构。在“没有相互重叠”的社团发现这一特例中,上述定义意为网络的节点可以很自然的划分为多个内部稠密连接、外部稀疏连接的节点簇。然而我们也允许“相互重叠”的社团存在。更加普适的定义基于如下原则:两个节点若是属于同一(多)个社团,那么他们之间更有可能相连,反之相连的可能性更小。另外一个相关但是不同的问题是社团搜索(community search),该问题的目标是找到某一特定顶点所属的社团。 性质 在计算机网络、信息网络、社会网络和生物网络等复杂网络的研究中,发现了网络的很多共同的特性,包括小世界性质、重尾度分布和集聚性质等等。另外一个普遍的特性便是社团结构。复杂网络中社团结构是指网络中节点聚簇的现象:同一簇内的节点稠密相连,而不同簇中的节点连接稀疏,正如右图所示。节点连接的这种不均质性表明网络内部具有某种天然的划分。

社团的定义通常依据节点集合的划分,也就是说每个节点属于且仅属于一个社团就如上图所示。这种简化非常有用,大多数社团发现方法都是找的这种社团结构。然而在某些情况下,节点同时属于好几个社团会是一种更好的社团表示方法。这种情况可能发生在一个社交网络中,其中一个节点代表一个人,社团代表不同的朋友群体:家人组成的社团、同事组成的社团、俱乐部朋友组成的社团等等。下文讨论的基于团的社团发现的方法,只是发现相互重叠的社团结构的一种方法。

有些网络可能不存在有意义的社团结构。很多基本网络模型,例如随机网络和BA模型,都没有展现出社团结构。

重要性 社团结构在真实网络中非常普遍。基于共同位置、兴趣和职业等,社交网络就能划分为很多不同团体(这也是“社团”这一术语的出处)。 找到一个网络潜在的社团结构(如果存在的话)是非常重要的,原因有很多。社团使得我们能对网络有一种大尺度的映射,因为单个社团在网络中表现的就像一个元点(meta-node)一样,研究起来更加容易。 单个社团还能阐明由该网络所表示的系统的功能,因为社团经常对应于系统中的功能性单元。在新陈代谢网络中,这种功能性对应于代谢循环和代谢路径;而在蛋白质相互作用网络中,社团对应于一个生物细胞中具有相似功能的蛋白质。类似的,引文网络通过研究主题形成社团。识别这些网络中的子机构,能够使我们洞察网络功能和拓扑结构是如何相互影响的。这种洞悉在帮助提升一些图上的算法(例如谱聚类算法)的性能时是非常有用的。 相比于网络的平均性质,社团通常具有非常不同的性质,这也是让社团结构如此重要的主要原因。因此,仅仅关注网络的平均性质,通常会错失很多网络中重要且有趣的特征。例如,在一个给定的社交网络中,爱交际和爱沉默的社团可能同时存在。 社团的存在通常也会影响网络上的各种传播过程,例如谣言传播和流行病传播。因此,要正确地理解这样的传播过程,在不同的情况下检测出社团并研究社团是如何影响传播过程是非常重要的。 最后,社团发现在网络科学中的一个重要应用是预测缺失连边和识别虚假连边。在数据测量过程中,由于一些原因,有些连边可能并没有观察到。同样的,有些虚假连边有可能被错误的收入了数据集中。这两种情况都能用社区发现的算法来处理,因为这类算法能够给出一对节点之间是否有连边的概率值。

社团发现的算法 在任意给定的网络中找出社团是一项计算非常困难的任务。网络中的社团的数量一般是未知的,社团的大小或者是密度也常常是不一样。然而尽管有这些困难,但还是有好些社区发现的算法被发展出来,并成功的应用到了多个方面。 最小切割方法 将网络划分成不同部分的最古老的算法之一是最小切割方法(minimum cut method)。例如,该方法用于并行计算的负载平衡,以便最小化处理器节点之间的通信。在最小切割方法中,网络被分成总数预先设定的部分,各部分通常具有大致相同的尺寸,算法选择使得组之间的连边数量最小化的划分方法。 在一些设计时就企图解决的问题上,该算法表现的很好,但它不太适合在一般网络中查找社区结构,因为该算法在找寻社团时忽视社团是否隐含在结构中,并且它只能找到固定数目的社团。 层次聚类 另外一个网络社团发现的算法是层次聚类。在该方法中,需要定义相似性度量,一遍量化节点对之间的某些(通常是拓扑)相似性。广泛使用的度量方法包括邻接矩阵每行之间的余弦相似性、Jaccard指标和汉明距离。然后就可以按照该度量方法,将一组相同节点放入同一社团。有几个常用的方案来执行分组操作,最简单的两个分别是单联聚类和全联聚类。单联聚类中,两个分组不同当且仅当组间节点对的相似性都小于一个给定的阈值。全联聚类中,组内节点对的相似性都高于一个给定的阈值。该方向一个新颖的方法是使用多种相似或者不相似度量,通过凸集组合在一起,能有效的提高这种方法论的性能。 Girvan-Newman算法 另外一个常用的社团发现的算法是Girvan-Newman算法(GN算法)。该算法识别出社团之间的连边,然后移除它们,只留下社团本身。识别过程利用了图论中的介数中心性度量(betweenness centrality),该度量会给每条边赋予一个数,当该边的介数很大时,该数也相应变大。

GN算法能的得到令人满意的结果,因为该方法在很多标准软件包中都被实现,使得该方法很流行。但是该方法运行的很慢,在有n个节点和m条的网络上需要花费O(m2n)的运行时间,使其处理大网络变得很不现实。 模块度最大化 抛开其已知的缺点,模块度最大化(modularity maxmization)是社团发现使用最广泛的方法之一。模块度是衡量网络某个社团划分好坏的效益函数。模块度最大化方法通过寻找一个或者多个具有较高模块度的网络划分来完成社团发现任务。因为对所有的划分就行遍历搜索十分不现实,实际使用的模块度最大化算法会结合近似最优化方法使用,例如贪婪算法、遗传算法或者光谱优化,不同的优化方法在速度和准确度之间取得不同的折中。一个比较流行的模块度最后化方法是Louvain方法:通过反复迭代来优化局部社团结构,直到在当前社团状态给一定扰动,全局模块度也不能再有所提升。目前最好的模块度最大化算法是迭代集合算法(iterative ensemble algorithm)。 模块度优化的有效性值得怀疑,因为已经表明,模块度优化通常无法检测出小于某种规模的社团,具体取决于网络规模的大小;另一方面,模块度值整体特征由具有高模块度值(接近绝对最大值)的划分的巨大退化所决定,有可能导致彼此非常不同。

统计推断 基于统计推断的模型试图将网络数据和一个生成模型进行拟合,该生成模型编码了社团结构。总来来说,该方法和其他可选方法的优势在于其更加公理化的本质,具有能解决统计显著性的天然能力。文献中的大多数方法都基于随机块模型(stochastic block model)以及包括混合成员(mixed membership),度校正(degree-correction)和层次结构的变体。可以通过原则性方法来完成统计模型的选择,例如最小描述长度(等价地,贝叶斯准则)和似然比检验。如今,存在很多算法来执行随机快模型的有效推断,包括置信传播和综合的蒙特卡洛方法。 与那些试图在给定目标函数的情况下对网络聚类的方法相比,这类方法基于生成模型,其不仅用作对网络的大规模结构的描述,而且还可用于概括数据并预测网络中丢失或虚假的链路。 基于团的方法 若子图中所有点都和该子图中其他店相互连接,那么该子图称之为团(clique)。因为节点之间相互连接程度不能比团更加紧密,所以毫不奇怪会有一些社区检测的方法是基于找图中的团和分析他们是如何重叠的。需要注意的是一个节点可能属于多个团,导致一个节点有可能属于多个社团,最后得到的是一个相互重叠的社团结构。 有一种方法是找寻最大团,该团不能是任何其他团的子图。相关的经典算法是Bron-Kerbosch算法。他们的重叠可以以多种方式定义社区。最简单的方法是仅考虑大于最小尺寸(节点数)的最大集团。然后,这些团的并集定义了一个子图,然后其组成(断开的部分)定义社区。这些方法通常在诸如UCInet的社交网络分析软件中被实现。 另外一种方法使用固定大小为k的团。他们的重叠可以用来定义一类k正则超图(k-regular hypergraph)或者团图(clique graph)的一般化结构。团图的节点代表原始图中的团,而边则记录原图中团之间的重叠信息。将任意社区发现的算法应用到团图上就可以将每个团都赋给一个社团。这样就可以用来决定团中节点的社团资格。再说一遍,因为一个节点可能在多个团中,所以它也有可能被分到多个社团中。例如团渗流算法将社团定义为k阶团的渗流集群(percolation clusters)。为此,该算法找出网络中所有的k阶团,也就是包含k个点的完全子图。然后定义快两个k阶团为相邻的,如果这两个团共享k-1个节点,也就是在定义团图中的边。然后社区就定义为k阶团的最大并集,在该并集中,我们能从一个k阶团通过一系列的k阶团连接到达任何一个k阶团。也就是说,社团就是团图中相连的部分。因为一个节点能属于多个不同的k阶团渗流集群,所以社团相互之间能有重叠。 社团发现算法的测试方法 评估算法在发现社团时的好坏仍旧是一个开放的问题。需要基于已知结构网络的分析。一个经典的例子是“four groups”测试,该测试中网络被分为四个相同尺寸的社团,社团之间的连接概率多变,从而为社团发现算法提供不同难度的网络结构。这种基准图是Condon和Karp提出的模型的特例,更一般来说是随机快模型(stochastic block models)的特例,是一类包含社团结构的随机图。其他更灵活的基准图也已经被提出来了,允许改变社团大小和存在非平凡的度分布,比如Lancichinetti等人提出的LFR基准。该基准是four groups的扩展,允许节点度分布和社团大小的异质性,使其成为社团检测算法更加严格的测试。Qasim Pasta和Faraz Zaidi在他们关于基于演化动力学而不是配置模型的基准模型上社区检测算法性能的论文中提出的一个重要问题。 常用的计算机生成的基准测试始于一个明确定义社区的网络。然后该网络的结构会通过重连或者移除边来破坏,使得社团检测算法越来越难检测出原始的划分。最后,网络会变得足够随机。这类基准有可能被称为“”open”。在这类基准上的表现通过测量标准化的互信息或者信息变差来估计。通过比较算法得到的社团划分和原始社团划分,来估计两个划分的相似度。 可检测性 近年来,许多研究团队发现了一个非常令人惊奇的结果:社团检测问题中存在相变过程,表明随着社团内部和外部的之间的连接变得越来越相等或者稀疏,社团突然变得不可检测了。在某种意义上,社团仍旧存在,因为边的存在和确实和点的社团资格还是有关系;但是在信息理论上不能可能再更好的标记节点,甚至不能和没有社区结构的生成图区分开来。这种相变和社区检测算法是没有关系的,表明存在一个网络中社区检测的基本能力极限,即使是用上了最优贝叶斯推断。

考虑一个随机块模型,有n个节点,q=2个相同大小的社团。让Pin和Pout分别表示社团内部和外部的连接概率。如果Pin>Pout, 那么网络就会因为集群内的连接稠密、相互之间连接稀疏而形成社团结构。在稀疏连接的情况下,pin和pout的尺度为O(1/n),所以平均度为常数: pin = cin/n 和 pout = cout/n 而当 图片: image.png 探测社团结构变得不现实。

个人工具
名字空间
操作
导航
工具箱