“社团结构”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第93行： 第93行：
  
  
−
在任意网络中检测社团可能是一项困难的计算任务。 网络中的社团数目(如果存在的话)通常是未知的，且社团规模和密度往往不同。尽管存在这些困难，一些检测社团的方法已经被发展和应用，并取得了不同程度的成功。
+
在任意网络中检测社团可能是一项困难的计算任务。 网络中的社团数目(如果存在的话)通常是未知的，且社团规模和密度往往不同。尽管存在这些困难，一些检测社团的方法已经被发展和应用，并取得了不同程度的成功。<ref name = Notices/>
  
 
===最小割法===
 
===最小割法===
第101行： 第101行：
  
  
−
在最小割法中，网络被分割成预定数量且大小相似的部分，选择这些部分使得节点组之间的边数达到最小。这种算法在许多应用程序中运行良好，但并不适用于检测一般网络中的社团结构，因为不论社团是否隐含在结构中，它只能找到数目固定的社团，而社团的数目通常是未知的。
+
在最小割法中，网络被分割成预定数量且大小相似的部分，选择这些部分使得节点组之间的边数达到最小。这种算法在许多应用程序中运行良好，但并不适用于检测一般网络中的社团结构，因为不论社团是否隐含在结构中，它只能找到数目固定的社团，而社团的数目通常是未知的。{{cite journal
 +
| author = M. E. J. Newman
 +
| year = 2004
 +
| title = Detecting community structure in networks
 +
| journal = Eur. Phys. J. B
 +
| volume = 38
 +
| issue = 2
 +
| pages = 321–330
 +
| doi = 10.1140/epjb/e2004-00124-y
 +
| bibcode = 2004EPJB...38..321N
 +
| hdl = 2027.42/43867
 +
}}
 +
</ref>
  
  
第110行： 第122行：
  
  
−
有几种常见的分组方案，其中最简单的两种是单链接聚类和'''完全链接聚类  Complete linkage clustering '''。前者在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团; 后者则是在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组。 一个有趣的方法是使用各种相似或不同的测度，通过'''凸和  convex sums '''来改进层次聚类的性能。
+
有几种常见的分组方案，其中最简单的两种是单链接聚类和'''完全链接聚类  Complete linkage clustering '''。前者在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团; 后者则是在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组。 一个有趣的方法是使用各种相似或不同的测度，通过'''凸和  convex sums '''来改进层次聚类的性能。<ref>{{Cite journal|title = Weighting dissimilarities to detect communities in networks|journal = Phil. Trans. R. Soc. A|date = 2015-12-13|issn = 1364-503X|pmid = 26527808|pages = 20150108|volume = 373|issue = 2056|doi = 10.1098/rsta.2015.0108|first = Alejandro J.|last = Alvarez|first2 = Carlos E.|last2 = Sanz-Rodríguez|first3 = Juan Luis|last3 = Cabrera|bibcode = 2015RSPTA.37350108A}}</ref>
  
  
第117行： 第129行：
  
  
−
另一个常见的社团检测算法是 '''Girvan-Newman 算法  Girvan–Newman algorithm  '''：首先识别社群之间连接的边，然后去除这些边，留下的就是社团。 该方法利用图论中的中心性度量来进行识别，当边位于多对节点之间时，给每条边赋予一个较大的数字。
+
另一个常见的社团检测算法是 '''Girvan-Newman 算法  Girvan–Newman algorithm  '''<ref name=ComSocBio/> ：首先识别社群之间连接的边，然后去除这些边，留下的就是社团。 该方法利用图论中的中心性度量来进行识别，当边位于多对节点之间时，给每条边赋予一个较大的数字。
  
  
−
'''Girvan-Newman算法'''返回的结果具有较好的质量，且由于它与许多标准软件包兼容，因此得到广泛应用。但其运行缓慢，在''n''个顶点和''m''条边的网络上耗费时长为''O(m2n)''，导致其并不适用于超过几千个节点的网络。
+
'''Girvan-Newman算法'''返回的结果具有较好的质量，且由于它与许多标准软件包兼容，因此得到广泛应用。但其运行缓慢，在''n''个顶点和''m''条边的网络上耗费时长为''O(m2n)''，导致其并不适用于超过几千个节点的网络。<ref name=fast>
 +
{{cite journal
 +
| author = M. E. J. Newman
 +
| year = 2004
 +
| title = Fast algorithm for detecting community structure in networks
 +
| journal = Phys. Rev. E
 +
| volume = 69
 +
| issue = 6
 +
| pages = 066133
 +
| doi = 10.1103/PhysRevE.69.066133
 +
| pmid = 15244693
 +
| arxiv = cond-mat/0309508
 +
| bibcode = 2004PhRvE..69f6133N
 +
}}
 +
</ref>
 +
 
  
 
===模板度最大值===
 
===模板度最大值===
  
  
−
尽管模板度最大值法有着它众所周知的缺点，但它依然是用于使用最为广泛的社团检测算法之一。 [[模块度  Modularity]]是一种衡量社团划分质量的标准，也是一个利益函数。 模块度最大值法通过搜索一个或多个具有特别高的模块化的网络的可能划分来检测社团。由于对所有可能的划分进行穷举搜索十分困难，所以实际的算法都是基于近似优化方法，如贪婪算法，模拟退火或光谱优化。不同的算法使得检测速度和准确性之间达到不同类型的平衡。 一种流行的模块度最大值法是 '''Louvain 算法  Louvain method '''，该算法迭代地优化本地社团，直到社团状态不再变化、全局模块化不能够再得到改善。 一个利用RenEEL的算法是当前最优良的模块度最大值算法，该算法是一个极值集成学习'''EEL范式  Extremal Ensemble Learning  paradigm  '''的例子。
+
尽管模板度最大值法有着它众所周知的缺点，但它依然是用于使用最为广泛的社团检测算法之一。<ref name=fast/>  [[模块度  Modularity]]是一种衡量社团划分质量的标准，也是一个利益函数。 模块度最大值法通过搜索一个或多个具有特别高的模块化的网络的可能划分来检测社团。由于对所有可能的划分进行穷举搜索十分困难，所以实际的算法都是基于近似优化方法，如贪婪算法，模拟退火或光谱优化。不同的算法使得检测速度和准确性之间达到不同类型的平衡。<ref>
 +
{{cite journal
 +
|author1=L. Danon |author2=J. Duch |author3=A. Díaz-Guilera |author4=A. Arenas | year = 2005
 +
| title = Comparing community structure identification
 +
| journal = J. Stat. Mech.
 +
| volume = 2005
 +
| issue = 9
 +
| pages = P09008
 +
| doi = 10.1088/1742-5468/2005/09/P09008
 +
|arxiv=cond-mat/0505245|bibcode=2005JSMTE..09..008D}}
 +
</ref><ref>
 +
{{cite journal
 +
|author1=R. Guimera |author2=L. A. N. Amaral | year = 2005
 +
| title = Functional cartography of complex metabolic networks
 +
| journal = Nature
 +
| volume = 433
 +
| pages = 895–900
 +
| doi = 10.1038/nature03288
 +
| issue=7028
 +
| pmid=15729348
 +
| pmc=2175124
 +
| arxiv=q-bio/0502035| bibcode=2005Natur.433..895G}}
 +
</ref> 一种流行的模块度最大值法是 '''Louvain 算法  Louvain method '''，该算法迭代地优化本地社团，直到社团状态不再变化、全局模块化不能够再得到改善。<ref>
 +
{{cite journal
 +
|author1=V.D. Blondel |author2=J.-L. Guillaume |author3=R. Lambiotte |author4=E. Lefebvre | year = 2008
 +
| title =  Fast unfolding of community hierarchies in large networks
 +
| journal = J. Stat. Mech.
 +
| volume = 2008
 +
| issue = 10
 +
| pages = P10008
 +
| doi = 10.1088/1742-5468/2008/10/P10008
 +
|arxiv=0803.0476|bibcode=2008JSMTE..10..008B}}
 +
</ref><ref>{{cite web|title=Lightning-fast Community Detection in Social Media: A Scalable Implementation of the Louvain Algorithm|url=https://pdfs.semanticscholar.org/9fa0/3cde48aee448bef4de225cc1f4943ab72095.pdf|date=2013}}</ref>一个利用RenEEL的算法是当前最优良的模块度最大值算法，该算法是一个极值集成学习'''EEL范式  Extremal Ensemble Learning  paradigm  '''的例子。<ref>
 +
{{cite journal
 +
|author1=J. Guo |author2=P. Singh | author3=K.E. Bassler | year = 2019
 +
| title = Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
 +
| journal = Scientific Reports
 +
| volume = 9
 +
| doi = 10.1038/s41598-019-50739-3
 +
| issue = 14234
 +
}}
 +
</ref>
 +
<ref name="RenEEL-Modularity">{{cite web|title=RenEEL-Modularity|url=https://github.com/kbassler/RenEEL-Modularity}}
 +
</ref>
  
  
−
模块度优化的有效性是值得怀疑的，因为已经证明模块度优化受分辨率的大小限制，这导致我们往往不能检测到比某个规模更小的集群； 另一方面，由于模块度值表征着具有高模块化的大量分区的简并度，接近绝对最大值，这可能与其他算法非常的不同。
+
模块度优化的有效性是值得怀疑的，因为已经证明模块度优化受分辨率的大小限制，这导致我们往往不能检测到比某个规模更小的集群；<ref>
 +
{{cite journal
 +
|author1=S. Fortunato |author2=M. Barthelemy | year = 2007
 +
| title = Resolution limit in community detection
 +
| journal = Proceedings of the National Academy of Sciences of the United States of America
 +
| volume = 104
 +
| pages = 36–41
 +
| pmid = 17190818
 +
| doi = 10.1073/pnas.0605965104
 +
| issue = 1
 +
| pmc = 1765466
 +
| arxiv = physics/0607100| bibcode = 2007PNAS..104...36F}}
 +
</ref>) 另一方面，由于模块度值表征着具有高模块化的大量分区的简并度，接近绝对最大值，这可能与其他算法非常的不同。<ref>
 +
{{cite journal
 +
|author1=B. H. Good |author2=Y.-A. de Montjoye |author3=A. Clauset | year = 2010
 +
| title = The performance of modularity maximization in practical contexts
 +
| journal = Phys. Rev. E
 +
| volume = 81
 +
| issue = 4
 +
| pages = 046106
 +
| doi = 10.1103/PhysRevE.81.046106
 +
|pmid=20481785 |arxiv=0910.0165|bibcode=2010PhRvE..81d6106G}}
 +
</ref>
  
 
===基于推论统计学的社团检测算法===
 
===基于推论统计学的社团检测算法===
  
  
−
基于'''推论统计学  statistical inference ''' 的算法试图将'''生成模型数据  generative model '''和能对社团结构进行编码的网络数据相匹配。 与其他办法相比，这种办法的总体优势在于其原则性更强，而且有能力从根本上解决具有统计意义的问题。 文献中的算法大多是基于'''随机块模型  The stochastic block model '''以及混合隶属度、程度校正、层次结构等变量。 模型选择可以使用一些有原则的算法，例如最小描述长度(或贝叶斯模型选择)和似然比检定。 目前有许多算法可以对随机块模型进行有效的推理，包括置信传播和凝聚蒙特卡罗算法。与尝试给定目标函数对网络进行聚类的算法不同，这类算法是基于生成模型的。生成模型不仅可以描述网络的大规模结构，而且可以用来归纳数据和发现网络中的缺失或虚假链路。
+
基于'''推论统计学  statistical inference ''' 的算法试图将'''生成模型数据  generative model '''和能对社团结构进行编码的网络数据相匹配。 与其他办法相比，这种办法的总体优势在于其原则性更强，而且有能力从根本上解决具有统计意义的问题。 文献中的算法大多是基于'''随机块模型  The stochastic block model '''<ref>
 +
{{Cite journal
 +
| doi = 10.1016/0378-8733(83)90021-7
 +
| issn = 0378-8733
 +
| volume = 5
 +
| issue = 2
 +
| pages = 109–137
 +
| last = Holland
 +
| first = Paul W.
 +
| author2 = Kathryn Blackmond Laskey| author3 =  Samuel Leinhardt
 +
| title = Stochastic blockmodels: First steps
 +
| journal = Social Networks
 +
| date = June 1983
 +
}}
 +
</ref>以及混合隶属度<ref>{{Cite journal
 +
| issn = 1532-4435
 +
| volume = 9
 +
| pages = 1981–2014
 +
| last = Airoldi
 +
| first = Edoardo M. |authorlink1=Edoardo Airoldi
 +
|author2=David M. Blei |author3=Stephen E. Fienberg |author4=Eric P. Xing
 +
| title = Mixed Membership Stochastic Blockmodels
 +
| journal = J. Mach. Learn. Res.
 +
| accessdate = 2013-10-09
 +
| date = June 2008
 +
| url = http://dl.acm.org/citation.cfm?id=1390681.1442798
 +
| pmid = 21701698
 +
| pmc = 3119541
 +
}}
 +
</ref><ref>
 +
{{Cite journal
 +
| doi = 10.1103/PhysRevE.84.036103
 +
| pmid = 22060452
 +
| volume = 84
 +
| issue = 3
 +
| pages = 036103
 +
| last = Ball
 +
| first = Brian
 +
|author2=Brian Karrer |author3=M. E. J. Newman
 +
| title = Efficient and principled method for detecting communities in networks
 +
| journal = Physical Review E
 +
| date = 2011
 +
| arxiv = 1104.3590
 +
| bibcode = 2011PhRvE..84c6103B
 +
}}
 +
</ref>、程度校正<ref>
 +
{{Cite journal
 +
| doi = 10.1103/PhysRevE.83.016107
 +
| pmid = 21405744
 +
| volume = 83
 +
| issue = 1
 +
| pages = 016107
 +
| last = Karrer
 +
| first = Brian
 +
|author2=M. E. J. Newman
 +
| title = Stochastic blockmodels and community structure in networks
 +
| journal = Physical Review E
 +
| date = 2011-01-21
 +
| arxiv = 1008.3926
 +
| bibcode = 2011PhRvE..83a6107K
 +
}}
 +
</ref>、层次结构等变量<ref>
 +
{{Cite journal
 +
| doi = 10.1103/PhysRevX.4.011047
 +
| volume = 4
 +
| issue = 1
 +
| pages = 011047
 +
| last = Peixoto
 +
| first = Tiago P.
 +
| title = Hierarchical Block Structures and High-Resolution Model Selection in Large Networks
 +
| journal = Physical Review X
 +
| date = 2014-03-24
 +
| arxiv = 1310.4377
 +
| bibcode = 2014PhRvX...4a1047P
 +
}}</ref>。 模型选择可以使用一些有原则的算法，例如最小描述长度(或贝叶斯模型选择<ref>{{cite arxiv|last=P. Peixoto|first=T.|date=2017|title=Bayesian stochastic blockmodeling|eprint=1705.10225|class=stat.ML}}</ref>)和似然比检定<ref>
 +
{{cite journal
 +
| last = Yan
 +
| first = Xiaoran
 +
|author2=Jacob E. Jensen |author3=Florent Krzakala |author4=Cristopher Moore |author5=Cosma Rohilla Shalizi |author6= Lenka Zdeborová|author6-link= Lenka Zdeborová |author7=Pan Zhang |author8=Yaojia Zhu
 +
| title = Model Selection for Degree-corrected Block Models
 +
|arxiv= 1207.3994
 +
| date = 2012-07-17 | doi=10.1088/1742-5468/2014/05/P05007 | pmid = 26167197
 +
| pmc = 4498413
 +
| volume=2014 | issue = 5
 +
| journal=Journal of Statistical Mechanics: Theory and Experiment | page=P05007
 +
|bibcode=2014JSMTE..05..007Y}}</ref>。 目前有许多算法可以对随机块模型进行有效的推理，包括置信传播<ref>
 +
{{Cite journal
 +
| doi = 10.1073/pnas.1221839110
 +
| issn = 0027-8424
 +
| volume = 110
 +
| issue = 36
 +
| pages = 14534–14539
 +
| last = Gopalan
 +
| first = Prem K.
 +
|author2=David M. Blei
 +
| title = Efficient discovery of overlapping communities in massive networks
 +
| journal = Proceedings of the National Academy of Sciences
 +
| date = 2013-09-03
 +
| pmid = 23950224
 +
| pmc=3767539
 +
| bibcode = 2013PNAS..11014534G
 +
}}</ref><ref>
 +
{{Cite journal
 +
| doi = 10.1103/PhysRevE.84.066106
 +
| pmid = 22304154
 +
| volume = 84
 +
| issue = 6
 +
| pages = 066106
 +
| last = Decelle
 +
| first = Aurelien
 +
|author2=Florent Krzakala |author3=Cristopher Moore |author4=Lenka Zdeborová|author4-link= Lenka Zdeborová
 +
| title = Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
 +
| journal = Physical Review E
 +
| date = 2011-12-12
 +
| arxiv = 1109.3041
 +
| bibcode = 2011PhRvE..84f6106D
 +
}}
 +
</ref>和凝聚蒙特卡罗算法<ref>{{Cite journal
 +
| doi = 10.1103/PhysRevE.89.012804
 +
| pmid = 24580278
 +
| volume = 89
 +
| issue = 1
 +
| pages = 012804
 +
| last = Peixoto
 +
| first = Tiago P.
 +
| title = Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
 +
| journal = Physical Review E
 +
| date = 2014-01-13
 +
| arxiv = 1310.4378
 +
| bibcode = 2014PhRvE..89a2804P
 +
}}
 +
</ref>。与尝试给定目标函数对网络进行聚类的算法不同，这类算法是基于生成模型的。生成模型不仅可以描述网络的大规模结构，而且可以用来归纳数据和发现网络中的缺失或虚假链路。<ref>{{Cite journal
 +
| doi = 10.1073/pnas.0908366106
 +
| volume = 106
 +
| issue = 52
 +
| pages = 22073–22078
 +
| last = Guimerà
 +
| first = Roger
 +
|author2=Marta Sales-Pardo
 +
| title = Missing and spurious interactions and the reconstruction of complex networks
 +
| journal = Proceedings of the National Academy of Sciences
 +
| date = 2009-12-29
 +
| pmid=20018705
 +
| pmc=2799723
 +
| arxiv = 1004.4791
 +
| bibcode = 2009PNAS..10622073G
 +
}}</ref><ref>
 +
{{Cite journal
 +
| issn = 0028-0836
 +
| volume = 453
 +
| issue = 7191
 +
| pages = 98–101
 +
| last = Clauset
 +
| first = Aaron
 +
| author2=Cristopher Moore |author3=M. E. J. Newman
 +
| title = Hierarchical structure and the prediction of missing links in networks
 +
| journal = Nature
 +
| date = 2008-05-01
 +
| doi = 10.1038/nature06830
 +
| pmid=18451861
 +
| arxiv = 0811.0484
 +
| bibcode = 2008Natur.453...98C
 +
}}
 +
</ref>
 +
 
  
 
===基于团结构的社团检测算法===
 
===基于团结构的社团检测算法===
第141行： 第397行：
  
  
−
如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图的'''极大团  maximal clique''' 。基于团的社团检测算法其中的一种方法就是找到“极大团” 。(其简单思想是：生成原始图的所有子图(可能有2n-1个子图，n表示节点个数）→判断这些子图是不是团→删除非极大团的其他团）其中， '''Bron-Kerbosch 算法  The Bron–Kerbosch algorithm  ''' 是找到极大团的经典算法之一。 最简单的方法是只考虑大于最小尺寸(节点数)的极大团。 这些团体的联合被定义为一个子图，其组件(断开的部分)被定义为社团。 这些算法通常在诸如 UCInet 这样的'''社交网络分析软件  social network analysis software  '''中实现。
+
如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图的'''极大团  maximal clique''' 。基于团的社团检测算法其中的一种方法就是找到“极大团” 。(其简单思想是：生成原始图的所有子图(可能有2n-1个子图，n表示节点个数）→判断这些子图是不是团→删除非极大团的其他团）其中， '''Bron-Kerbosch 算法  The Bron–Kerbosch algorithm  ''' 是找到极大团的经典算法之一。 最简单的方法是只考虑大于最小尺寸(节点数)的极大团。 这些团体的联合被定义为一个子图，其组件(断开的部分)被定义为社团。<ref name="Everett1998">
 +
{{cite journal
 +
|author1=M.G. Everett |author2=S.P. Borgatti | year = 1998
 +
| title = Analyzing Clique Overlap Connections
 +
| journal = Connections
 +
| volume = 21
 +
| pages = 49
 +
}}
 +
</ref>  这些算法通常在诸如 UCInet 这样的'''社交网络分析软件  social network analysis software  '''中实现。
  
  
−
另一种方法是使用固定大小的团体，设大小为''k''。 这些图的重叠可以用来定义一类 ''k''- 正则超图或一种团图（线图的一种推广，此时''k''=2）。团图的节点表示原始图中的团，而团图的边则记录原始图中团的重叠。将以前的社团检测算法(将每个节点分配给社团)应用到团图，然后将每个团图分配给社团，进而可以使用它来确定派系中节点间的关系。同样，由于节点可能处于多个小团体中，所以它可以是多个社团的成员。例如，'''团渗透算法  clique percolation '''将社团定义为 ''k''-clique的渗透集群。 为了做到这一点，需找到一个网络中的所有 ''k'' 派系，即所有完整子图的 ''k'' 个节点。然后定义两个共享 ''k-1''个节点的 '''''k''-cliques  ''k'' -团 '''为相邻的 ''k''-cliques，即用于定义团图中的边。然后将社团定义为''k''-clique的最大并集，其中任意 ''k''-clique 可以通过一系列''k''-clique邻接，从任意''k''-clique 到达其他''k''-clique 。 也就是说，社团只是团图中的连通组件。 由于一个节点可以同时属于几个不同的''k''-clique渗透簇，故社团之间可以相互重叠。
+
另一种方法是使用固定大小的团体，设大小为<math>k</math>。 这些图的重叠可以用来定义一类 <math>k</math>- 正则超图或一种团图（线图的一种推广，此时<math>k=2</math>）。<ref name="Evans2010">{{cite journal
 +
| author = T.S. Evans
 +
| year = 2010
 +
| title = Clique Graphs and Overlapping Communities
 +
| journal = J. Stat. Mech.
 +
| pages = P12037
 +
| doi = 10.1088/1742-5468/2010/12/P12037
 +
| arxiv = 1009.0638
 +
| volume=2010
 +
| issue=12
 +
| bibcode = 2010JSMTE..12..037E
 +
}}
 +
</ref> 团图的节点表示原始图中的团，而团图的边则记录原始图中团的重叠。将以前的社团检测算法(将每个节点分配给社团)应用到团图，然后将每个团图分配给社团，进而可以使用它来确定派系中节点间的关系。同样，由于节点可能处于多个小团体中，所以它可以是多个社团的成员。例如，'''团渗透算法  clique percolation '''<ref>
 +
{{cite journal
 +
|author1=G. Palla |author2=I. Derényi |author3=I. Farkas |author4=T. Vicsek | year = 2005
 +
| title = Uncovering the overlapping community structure of complex networks in nature and society
 +
| journal = Nature
 +
| pmid = 15944704
 +
| volume = 435
 +
| issue = 7043
 +
| pages = 814–818
 +
| doi = 10.1038/nature03607
 +
|arxiv=physics/0506133|bibcode=2005Natur.435..814P}}
 +
</ref>将社团定义为<math>k</math>-clique的渗透集群。 为了做到这一点，需找到一个网络中的所有 <math>k</math>派系，即所有完整子图的 <math>k</math> 个节点。然后定义两个共享 <math>k-1</math>个节点的 '''<math>k</math>-cliques  <math>k</math> -团 '''为相邻的<math>k</math>-cliques，即用于定义团图中的边。然后将社团定义为<math>k</math>-clique的最大并集，其中任意<math>k</math>-clique 可以通过一系列<math>k</math>-clique邻接，从任意<math>k</math>-clique 到达其他<math>k</math>-clique 。也就是说，社团只是团图中的连通组件。 由于一个节点可以同时属于几个不同的<math>k</math>-clique渗透簇，故社团之间可以相互重叠。
  
 
==社团检测算法的评价标准==
 
==社团检测算法的评价标准==

2020年4月9日 (四) 22:42的版本


在网络科学研究中，如果某个网络中的节点可以轻易地被划分为若干个内部紧密连接的节点集（集合间可能重合），那么就可以说这个网络具有社团结构 Community structure。除节点集重叠的特殊情况下外，网络自然地被分成一个个节点集，这些节点集内部连接紧密，而节点集与节点集之间连接稀疏（但也存在节点集重叠的情况）。 更广泛的定义基于以下原则：即如果节点对同属一个社团，则更有可能相互连接；如果不属于同一个社团，则更不可能相互连接。 一个相关但不同的问题是社团搜索，其目标是找到某个节点所属的社团。


属性

在研究计算机、信息网络、社会网络和生物网络等网络时，经常发现网络具有许多不同的特征，包括小世界性 Small-world property、重尾度分布 Heavy-tailed degree distributions 和聚集性 Clustering 等。 而网络也具有共同特征——都具有社团结构。[1][2][3][4][5]社团结构指的是网络中内部连接比其余部分更加密集的节点组。 这种联系的不均匀性表明网络内部存在某种自然的划分。

将节点集进行划分，就产生了一个个社团。也就是说，每个节点被放入一个社团中，且该社团唯一，这是一个有用的简化，多数社团检测算法都适用于这种类型的社团结构。然而，在某些情况下，则是一个节点位于多个社团（即社团具有重叠性）的社团结构能够更好表示所研究的对象。这可能发生在社交网络中：每个节点代表一个人，而社团代表不同的朋友群体，如: 一个社团代表家庭，另一个社团代表同事，还有一个社团代表来自同一体育俱乐部的朋友等等。 下面所讨论的基于团结构的社团检测算法 Clique-based method 的例子,就属于这种具有重叠性的社团结构。


有些网络可能不具有任何有意义的社团结构。例如许多基本的网络模型，例如随机图 Random graph 和 Barabsi-Albert 模型 Barabási–Albert model 就不具有社团结构。

重要性

一个演示社团结构的小型网络示意图，包含三组内部紧密连接的节点，各组之间连接较为稀疏

社团结构在实际网络中相当常见，社会网络包括基于相同位置、兴趣、职业等的社团团体(实际上是这个术语的起源)。[5][6]


在网络中找到一个潜在的社团结构(如果它存在的话)是很重要的，原因如下：

第一，社团允许我们创建一个大范围的网络地图，因为单个社团就像网络中的元节点，这使得研究更加容易；[7]


第二，由于社团通常与系统的功能单元相对应，因此单个社团也能阐明网络所代表的系统功能。如在代谢网络中，这些功能组对应于周期或路径；而在蛋白质相互作用网络 Protein interaction network 中，社团对应于生物细胞内具有类似功能的蛋白质；在引用网络中，社团对应于研究主题。 而识别网络中的子结构，有助于深入了解网络的功能以及拓扑效应之间是如何相互影响的。这种见解对于改进谱聚类 Spectral clustering 等图的数据处理算法有一定的参考价值。[8]


第三，社团的重要性还体现在社团的属性通常与网络的普遍属性迥异。因此，只关注普遍属性通常会忽略网络内部许多重要且有趣的特性。例如，在一个给定的社交网络中，爱交际的群体和沉默寡言的群体可能同时存在。[7]


第四，社团的存在通常也会影响到传播过程，如在网络上发生的谣言传播或流行病传播。 因此，为了正确理解这些过程，最重要的就是检测社团，并研究它们如何在各种环境下影响传播过程。


最后，社团检测在网络科学中的一个重要应用是预测网络中的缺失链接和识别网络中的错误链接。 在测量过程中，由于多种原因，有些链接可能无法被观察到。同样，由于测量中的失误，一些链接可能会错误地输入数据。社团检测算法很好地处理了这两种情况，因为它允许给定节点对之间存在连边。[9]

社团检测算法

在任意网络中检测社团可能是一项困难的计算任务。 网络中的社团数目(如果存在的话)通常是未知的，且社团规模和密度往往不同。尽管存在这些困难，一些检测社团的方法已经被发展和应用，并取得了不同程度的成功。[4]

最小割法

将网络划分为若干部分的最古老的算法之一是最小割法(以及诸如比率割法和归一化割法等变体)。 此方法可用于并行计算的负载平衡，尽可能减少处理器节点之间的通信。


在最小割法中，网络被分割成预定数量且大小相似的部分，选择这些部分使得节点组之间的边数达到最小。这种算法在许多应用程序中运行良好，但并不适用于检测一般网络中的社团结构，因为不论社团是否隐含在结构中，它只能找到数目固定的社团，而社团的数目通常是未知的。M. E. J. Newman (2004). "Detecting community structure in networks". Eur. Phys. J. B. 38 (2): 321–330. Bibcode:2004EPJB...38..321N. doi:10.1140/epjb/e2004-00124-y. hdl:2027.42/43867. </ref>


层次聚类

在网络中检测社团结构的另一种方法是层次聚类 Hierarchical clustering 。 在这种算法中，定义了一种相似性度量 Similarity measure ，去量化节点对之间的某些(通常是拓扑的)相似性。 常用的测量方法包括余弦距离健康指数 Cosine similarity 、雅卡德指数 Jaccard index ,以及汉明距离健康指数邻接矩阵 Hamming distance between rows of the adjacency matrix 。 然后根据该算法将相似的节点分组到同一个社团中。


有几种常见的分组方案，其中最简单的两种是单链接聚类和完全链接聚类 Complete linkage clustering 。前者在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团; 后者则是在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组。 一个有趣的方法是使用各种相似或不同的测度，通过凸和 convex sums 来改进层次聚类的性能。[10]


Girvan-Newman 社团检测算法

另一个常见的社团检测算法是 Girvan-Newman 算法 Girvan–Newman algorithm [1] ：首先识别社群之间连接的边，然后去除这些边，留下的就是社团。 该方法利用图论中的中心性度量来进行识别，当边位于多对节点之间时，给每条边赋予一个较大的数字。


Girvan-Newman算法返回的结果具有较好的质量，且由于它与许多标准软件包兼容，因此得到广泛应用。但其运行缓慢，在n个顶点和m条边的网络上耗费时长为O(m2n)，导致其并不适用于超过几千个节点的网络。[11]


模板度最大值

尽管模板度最大值法有着它众所周知的缺点，但它依然是用于使用最为广泛的社团检测算法之一。[11] 模块度 Modularity是一种衡量社团划分质量的标准，也是一个利益函数。 模块度最大值法通过搜索一个或多个具有特别高的模块化的网络的可能划分来检测社团。由于对所有可能的划分进行穷举搜索十分困难，所以实际的算法都是基于近似优化方法，如贪婪算法，模拟退火或光谱优化。不同的算法使得检测速度和准确性之间达到不同类型的平衡。[12][13] 一种流行的模块度最大值法是 Louvain 算法 Louvain method ，该算法迭代地优化本地社团，直到社团状态不再变化、全局模块化不能够再得到改善。[14][15]一个利用RenEEL的算法是当前最优良的模块度最大值算法，该算法是一个极值集成学习EEL范式 Extremal Ensemble Learning paradigm 的例子。[16] [17]


模块度优化的有效性是值得怀疑的，因为已经证明模块度优化受分辨率的大小限制，这导致我们往往不能检测到比某个规模更小的集群；[18]) 另一方面，由于模块度值表征着具有高模块化的大量分区的简并度，接近绝对最大值，这可能与其他算法非常的不同。[19]

基于推论统计学的社团检测算法

基于推论统计学 statistical inference 的算法试图将生成模型数据 generative model 和能对社团结构进行编码的网络数据相匹配。 与其他办法相比，这种办法的总体优势在于其原则性更强，而且有能力从根本上解决具有统计意义的问题。 文献中的算法大多是基于随机块模型 The stochastic block model [20]以及混合隶属度[21][22]、程度校正[23]、层次结构等变量[24]。 模型选择可以使用一些有原则的算法，例如最小描述长度(或贝叶斯模型选择[25])和似然比检定[26]。 目前有许多算法可以对随机块模型进行有效的推理，包括置信传播[27][28]和凝聚蒙特卡罗算法[29]。与尝试给定目标函数对网络进行聚类的算法不同，这类算法是基于生成模型的。生成模型不仅可以描述网络的大规模结构，而且可以用来归纳数据和发现网络中的缺失或虚假链路。[30][31]


基于团结构的社团检测算法

团就是一个无向图的完全子图，团中的每个节点都与团中的其他节点相连。 由于节点之间的联系不可能比这更紧密，所以在网络中产生了很多基于团结构的社团检测算法，由此还可以分析具有重叠性的社团结构。在这些算法中，一个节点可以同时属于多个社团，从而形成一个“重叠的社团结构”。


如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图的极大团 maximal clique 。基于团的社团检测算法其中的一种方法就是找到“极大团” 。(其简单思想是：生成原始图的所有子图(可能有2n-1个子图，n表示节点个数）→判断这些子图是不是团→删除非极大团的其他团）其中， Bron-Kerbosch 算法 The Bron–Kerbosch algorithm 是找到极大团的经典算法之一。 最简单的方法是只考虑大于最小尺寸(节点数)的极大团。 这些团体的联合被定义为一个子图，其组件(断开的部分)被定义为社团。[32] 这些算法通常在诸如 UCInet 这样的社交网络分析软件 social network analysis software 中实现。


另一种方法是使用固定大小的团体，设大小为[math]\displaystyle{ k }[/math]。 这些图的重叠可以用来定义一类 [math]\displaystyle{ k }[/math]- 正则超图或一种团图（线图的一种推广，此时[math]\displaystyle{ k=2 }[/math]）。[33] 团图的节点表示原始图中的团，而团图的边则记录原始图中团的重叠。将以前的社团检测算法(将每个节点分配给社团)应用到团图，然后将每个团图分配给社团，进而可以使用它来确定派系中节点间的关系。同样，由于节点可能处于多个小团体中，所以它可以是多个社团的成员。例如，团渗透算法 clique percolation [34]将社团定义为[math]\displaystyle{ k }[/math]-clique的渗透集群。 为了做到这一点，需找到一个网络中的所有 [math]\displaystyle{ k }[/math]派系，即所有完整子图的 [math]\displaystyle{ k }[/math] 个节点。然后定义两个共享 [math]\displaystyle{ k-1 }[/math]个节点的 [math]\displaystyle{ k }[/math]-cliques [math]\displaystyle{ k }[/math] -团 为相邻的[math]\displaystyle{ k }[/math]-cliques，即用于定义团图中的边。然后将社团定义为[math]\displaystyle{ k }[/math]-clique的最大并集，其中任意[math]\displaystyle{ k }[/math]-clique 可以通过一系列[math]\displaystyle{ k }[/math]-clique邻接，从任意[math]\displaystyle{ k }[/math]-clique 到达其他[math]\displaystyle{ k }[/math]-clique 。也就是说，社团只是团图中的连通组件。 由于一个节点可以同时属于几个不同的[math]\displaystyle{ k }[/math]-clique渗透簇，故社团之间可以相互重叠。

社团检测算法的评价标准

如何对算法进行评价以判断哪些能够更好地检测到社团结构仍悬而未决，必须基于对已知结构的网络的分析。 一个典型的例子是”四组”测试，在这种测试中，一个网络被分成四个大小相等的组(通常每组32个节点) ，由于组内和组间连接的概率各不相同，导致出现了一些具有挑战性的社团结构，这为社团检测制造了一定难度。这样的基准图是康德 Condon 和 卡帕 Karp 的种植 l-分区模型 The planted l-partition model 的特例，或者也是“随机块模型” Stochastic block models （一类包含社团结构的随机网络模型）更一般的情形。此外，还提出了其他更灵活的基准测试，允许不同的组大小和非平凡度分布。例如 LFR 基准测试 LFR benchmark ，它是四组基准测试的扩展，包括节点度和社团大小的不同分布，能够更加严格地评价社团检测算法。


常用的计算机生成基准测试从定义良好的社团网络开始。这种结构由于重新布线或删除链接而退化，使得算法越来越难以检测到原始分区。最后，网络到达一个随机点。这种基准可以称为是“开放的”。这些基准的性能是通过标准化互信息 Normalized mutual information 或信息变化 Variation of information 等度量来评估的。 他们将算法得到的解与原来的社团结构进行比较，评估两个分区的相似性。

可探测性

近年来，在对各种社团的研究中，我们得到一个相当惊人的结果——社团检测问题存在阶段性转变，这表明随着社团内部和社团之间连接的密度越来越接近或两者都变得越来越小(由于社团结构变得太弱或网络变得太稀疏) ，社团就会突然变得无法检测。


从某种意义上说，社团本身仍然存在，因为边的存在和缺失仍然与其节点的社团成员关系密切；但是，从理论上讲，如果没有社团结构，就不可能更好地标记节点，甚至不可能将图与由Erdos-Renyi模型 Erdos–Renyi model 等空模型生成的图区分开来。这种转换与用于检测社团的算法类型无关，这意味着我们在网络中检测社团的能力存在根本的限制，即使我们使用最优的贝叶斯推理（而不考虑我们的计算资源）。


考虑一个具有 n 个节点，q=2 的相同组的随机块模型，并且设Putin (1).pngPutout.png分别是组内和组间的连接概率。


如果Ppppinpout.png，由于社团内部的链接密度大于群体之间的链接密度，网络将具有群体结构。


在稀疏情况下,Putin (1).png和Putout.png都以O n.png为比例，所以平均温度是恒定的，则有:

Pin n.png和Pppinot N.png


然后就不可能在下列情况检测到这些社团: Cin Cout.png

进一步阅读


相关链接

编者推荐

复杂网络课程中详细介绍了社团结构的定义、划分方法、空间结构

下是关于集智俱乐部关于社团结构的一些文章

若还想再进一步了解社团结构

本中文词条由趣木木用户参与编译，刘佩佩用户审校，Meng莫编辑，欢迎在讨论页面留言


本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

  1. ↑ 1.0 1.1 M. Girvan; M. E. J. Newman (2002). "Community structure in social and biological networks". Proc. Natl. Acad. Sci. USA. 99 (12): 7821–7826. arXiv:cond-mat/0112110. Bibcode:2002PNAS...99.7821G. doi:10.1073/pnas.122653799. PMC 122977. PMID 12060727.
  2. ↑ S. Fortunato (2010). "Community detection in graphs". Phys. Rep. 486 (3–5): 75–174. arXiv:0906.0612. Bibcode:2010PhR...486...75F. doi:10.1016/j.physrep.2009.11.002.
  3. ↑ F. D. Malliaros; M. Vazirgiannis (2013). "Clustering and community detection in directed networks: A survey". Phys. Rep. 533 (4): 95–142. arXiv:1308.0971. Bibcode:2013PhR...533...95M. doi:10.1016/j.physrep.2013.08.002.
  4. ↑ 4.0 4.1 M. A. Porter; J.-P. Onnela; P. J. Mucha (2009). "Communities in Networks" (PDF). Notices of the American Mathematical Society. 56: 1082–1097, 1164–1166.
  5. ↑ 5.0 5.1 Fani, Hossein; Bagheri, Ebrahim (2017). "Community detection in social networks". Encyclopedia with Semantic Computing and Robotic Intelligence. Vol. 1. pp. 1630001 [8]. doi:10.1142/S2425038416300019.
  6. ↑ Hamdaqa, Mohammad; Tahvildari, Ladan; LaChapelle, Neil; Campbell, Brian (2014). "Cultural Scene Detection Using Reverse Louvain Optimization" (PDF). Science of Computer Programming. 95: 44–72. doi:10.1016/j.scico.2014.01.006.
  7. ↑ 7.0 7.1 M.E.J.Neman (2006). "Finding community structure in networks using the eigenvectors of matrices". Phys. Rev. E. 74 (3): 1–19. arXiv:physics/0605087. Bibcode:2006PhRvE..74c6104N. doi:10.1103/PhysRevE.74.036104. PMID 17025705.
  8. ↑ Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). "Data reduction for spectral clustering to analyze high throughput flow cytometry data". BMC Bioinformatics. 11 (1): 403. doi:10.1186/1471-2105-11-403. PMC 2923634. PMID 20667133.
  9. ↑ Aaron Clauset; Cristopher Moore; M.E.J. Newman (2008). "Hierarchical structure and the prediction of missing links in networks". Nature. 453 (7191): 98–101. arXiv:0811.0484. Bibcode:2008Natur.453...98C. doi:10.1038/nature06830. PMID 18451861.
  10. ↑ Alvarez, Alejandro J.; Sanz-Rodríguez, Carlos E.; Cabrera, Juan Luis (2015-12-13). "Weighting dissimilarities to detect communities in networks". Phil. Trans. R. Soc. A. 373 (2056): 20150108. Bibcode:2015RSPTA.37350108A. doi:10.1098/rsta.2015.0108. ISSN 1364-503X. PMID 26527808.
  11. ↑ 11.0 11.1 M. E. J. Newman (2004). "Fast algorithm for detecting community structure in networks". Phys. Rev. E. 69 (6): 066133. arXiv:cond-mat/0309508. Bibcode:2004PhRvE..69f6133N. doi:10.1103/PhysRevE.69.066133. PMID 15244693.
  12. ↑ L. Danon; J. Duch; A. Díaz-Guilera; A. Arenas (2005). "Comparing community structure identification". J. Stat. Mech. 2005 (9): P09008. arXiv:cond-mat/0505245. Bibcode:2005JSMTE..09..008D. doi:10.1088/1742-5468/2005/09/P09008.
  13. ↑ R. Guimera; L. A. N. Amaral (2005). "Functional cartography of complex metabolic networks". Nature. 433 (7028): 895–900. arXiv:q-bio/0502035. Bibcode:2005Natur.433..895G. doi:10.1038/nature03288. PMC 2175124. PMID 15729348.
  14. ↑ V.D. Blondel; J.-L. Guillaume; R. Lambiotte; E. Lefebvre (2008). "Fast unfolding of community hierarchies in large networks". J. Stat. Mech. 2008 (10): P10008. arXiv:0803.0476. Bibcode:2008JSMTE..10..008B. doi:10.1088/1742-5468/2008/10/P10008.
  15. ↑ "Lightning-fast Community Detection in Social Media: A Scalable Implementation of the Louvain Algorithm" (PDF). 2013.
  16. ↑ J. Guo; P. Singh; K.E. Bassler (2019). "Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks". Scientific Reports. 9 (14234). doi:10.1038/s41598-019-50739-3.
  17. ↑ "RenEEL-Modularity".
  18. ↑ S. Fortunato; M. Barthelemy (2007). "Resolution limit in community detection". Proceedings of the National Academy of Sciences of the United States of America. 104 (1): 36–41. arXiv:physics/0607100. Bibcode:2007PNAS..104...36F. doi:10.1073/pnas.0605965104. PMC 1765466. PMID 17190818.
  19. ↑ B. H. Good; Y.-A. de Montjoye; A. Clauset (2010). "The performance of modularity maximization in practical contexts". Phys. Rev. E. 81 (4): 046106. arXiv:0910.0165. Bibcode:2010PhRvE..81d6106G. doi:10.1103/PhysRevE.81.046106. PMID 20481785.
  20. ↑ Holland, Paul W.; Kathryn Blackmond Laskey; Samuel Leinhardt (June 1983). "Stochastic blockmodels: First steps". Social Networks. 5 (2): 109–137. doi:10.1016/0378-8733(83)90021-7. ISSN 0378-8733.
  21. ↑ Airoldi, Edoardo M.; David M. Blei; Stephen E. Fienberg; Eric P. Xing (June 2008). "Mixed Membership Stochastic Blockmodels". J. Mach. Learn. Res. 9: 1981–2014. ISSN 1532-4435. PMC 3119541. PMID 21701698. Retrieved 2013-10-09.
  22. ↑ Ball, Brian; Brian Karrer; M. E. J. Newman (2011). "Efficient and principled method for detecting communities in networks". Physical Review E. 84 (3): 036103. arXiv:1104.3590. Bibcode:2011PhRvE..84c6103B. doi:10.1103/PhysRevE.84.036103. PMID 22060452.
  23. ↑ Karrer, Brian; M. E. J. Newman (2011-01-21). "Stochastic blockmodels and community structure in networks". Physical Review E. 83 (1): 016107. arXiv:1008.3926. Bibcode:2011PhRvE..83a6107K. doi:10.1103/PhysRevE.83.016107. PMID 21405744.
  24. ↑ Peixoto, Tiago P. (2014-03-24). "Hierarchical Block Structures and High-Resolution Model Selection in Large Networks". Physical Review X. 4 (1): 011047. arXiv:1310.4377. Bibcode:2014PhRvX...4a1047P. doi:10.1103/PhysRevX.4.011047.
  25. ↑ P. Peixoto, T. (2017). "Bayesian stochastic blockmodeling". arXiv:1705.10225 [stat.ML].
  26. ↑ Yan, Xiaoran; Jacob E. Jensen; Florent Krzakala; Cristopher Moore; Cosma Rohilla Shalizi; Lenka Zdeborová; Pan Zhang; Yaojia Zhu (2012-07-17). "Model Selection for Degree-corrected Block Models". Journal of Statistical Mechanics: Theory and Experiment. 2014 (5): P05007. arXiv:1207.3994. Bibcode:2014JSMTE..05..007Y. doi:10.1088/1742-5468/2014/05/P05007. PMC 4498413. PMID 26167197.
  27. ↑ Gopalan, Prem K.; David M. Blei (2013-09-03). "Efficient discovery of overlapping communities in massive networks". Proceedings of the National Academy of Sciences. 110 (36): 14534–14539. Bibcode:2013PNAS..11014534G. doi:10.1073/pnas.1221839110. ISSN 0027-8424. PMC 3767539. PMID 23950224.
  28. ↑ Decelle, Aurelien; Florent Krzakala; Cristopher Moore; Lenka Zdeborová (2011-12-12). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". Physical Review E. 84 (6): 066106. arXiv:1109.3041. Bibcode:2011PhRvE..84f6106D. doi:10.1103/PhysRevE.84.066106. PMID 22304154.
  29. ↑ Peixoto, Tiago P. (2014-01-13). "Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models". Physical Review E. 89 (1): 012804. arXiv:1310.4378. Bibcode:2014PhRvE..89a2804P. doi:10.1103/PhysRevE.89.012804. PMID 24580278.
  30. ↑ Guimerà, Roger; Marta Sales-Pardo (2009-12-29). "Missing and spurious interactions and the reconstruction of complex networks". Proceedings of the National Academy of Sciences. 106 (52): 22073–22078. arXiv:1004.4791. Bibcode:2009PNAS..10622073G. doi:10.1073/pnas.0908366106. PMC 2799723. PMID 20018705.
  31. ↑ Clauset, Aaron; Cristopher Moore; M. E. J. Newman (2008-05-01). "Hierarchical structure and the prediction of missing links in networks". Nature. 453 (7191): 98–101. arXiv:0811.0484. Bibcode:2008Natur.453...98C. doi:10.1038/nature06830. ISSN 0028-0836. PMID 18451861.
  32. ↑ M.G. Everett; S.P. Borgatti (1998). "Analyzing Clique Overlap Connections". Connections. 21: 49.
  33. ↑ T.S. Evans (2010). "Clique Graphs and Overlapping Communities". J. Stat. Mech. 2010 (12): P12037. arXiv:1009.0638. Bibcode:2010JSMTE..12..037E. doi:10.1088/1742-5468/2010/12/P12037.
  34. ↑ G. Palla; I. Derényi; I. Farkas; T. Vicsek (2005). "Uncovering the overlapping community structure of complex networks in nature and society". Nature. 435 (7043): 814–818. arXiv:physics/0506133. Bibcode:2005Natur.435..814P. doi:10.1038/nature03607. PMID 15944704.
取自“https://wiki.swarma.org/index.php?title=社团结构&oldid=2379”