简介
网络科学家Santo Fortunato和Mark Newman在《自然物理》杂志最近的一篇综述文章中，梳理了近20年来复杂网络社区检测领域的主要问题、方法和未来发展方向。本文是对本文的总结和解读。
研究领域:社区检测、网络科学、网络嵌入
徐莹|作者
邓一雪| 编辑
论文题目:
网络社区检测20年
论文地址:
https://www.nature.com/articles/s41567-022-01716-7
1。研究网络社区结构的必要性
网络存在于我们生活的许多方面，从个人关系的在线和离线社交网络，基因、代谢物和神经元之间相互作用的生物网络，到互联网、基础设施和交通网络等技术网络。
网络的一个显著特征是它们的社区结构——将节点组织成组，其中同一组中的节点紧密连接或共享相似的特征或角色(图1)。网络社区发现算法已经广泛应用于许多学科。
图一。社会网络的社区结构
节点是脸书用户，而边代表脸书友谊。使用
InfoMap算法发现用不同颜色表示的社区。
社区检测的早期研究可以追溯到20世纪80年代的社会学文献，但经过20年前格文和纽曼的工作，这个问题在物理学界引起了广泛关注。
2。社区检测的总体框架
在Santo Fortunato和Mark E.J.Newman最新发表在Nature Physics上的文章中，作者回顾了过去20年中网络社区结构检测的进展。主要包括以下工作-
2.1群体结构的定义
首先要明确的是，在大多数情况下，一个社区被定义为一组不重叠的节点，使得一个组中的边比它们之间的边多，但是这个定义还是留下了很多可能性，相应的也有很多计算方法。
2.2社区检测的主要方法概述
最常见的方法是基于优化。给网络的每个可能的社区划分赋值，让“好”的划分得到高分，然后寻找分数最高的划分。分配分数的方法有很多种。最流行的方法利用称为模块性的质量函数，它明确支持社区中具有许多边的分区。
近年来，另一种引起广泛关注的优化方法是基于统计推断。在这种方法中，社区不仅是网络结构的一个特征，也是一个主要的驱动因素:节点之间的连接正是因为它们所属的社区，就像社交网络中兴趣相似的人或主题相似的网页的情况一样。一个“好”的社区结构是模型以高概率生成的观察到的网络结构，所以这个概率可以作为一个评分函数来寻找最佳的社区划分。
第三种主要的社区检测算法依赖于社区结构和网络上的动态过程之间的关系，尤其是随机行走。因为网络中的社区之间通常只有稀疏的连接，网络上的随机游走倾向于在社区内游荡，所以随机游走的概率分布可以用来检测社区。
2.3全球和本地
虽然这些社区检测方法工作良好，但它们都依赖于整个网络结构，这并不总是理想的。
有时，人们可能只想知道小范围内的关联，并希望避免分析整个事件的计算负担。更重要的是，在某些情况下，对完整网络的关注可能会导致有问题的结果。比如模块化最大化返回的结果依赖于网络的整体规模，产生了所谓的分辨率限制，类似的限制也出现在其他方法中。这些问题可以通过引入控制分辨率规模的参数来缓解，或者通过构建嵌套的层次结构来允许人们探索更小的社区规模。然而，另一种选择是使用本地方法进行社区检测。工作原理通常是围绕指定的种子节点建立单个社区，贪婪地添加节点，直到达到一个质量函数的局部最优值。这是一种计算效率高的方法。
2.4基准测试和性能测试
鉴于社区检测的大量竞争方法，一个关键问题是如何在它们之间进行选择。
性能通常通过算法在人工参考网络中恢复已知社区的成功来衡量。为了解决这个问题，已经提出了更现实的SBM变体，例如程度校正的SBM和LFR模型，其已经成为近年来的标准基准。算法在这些网络中恢复已知社区的成功通常通过使用信息论度量来估计，例如标准互信息。
上述所有方法通常在基准测试中都有不错的表现，尽管当测试网络中的社区结构变弱时会出现有趣的转折。然而令人惊讶的是，社区检测居然还没走到这一步就失败了:参数空中有一个非零大小的区域，在这个区域中，网络中存在社区，但是算法找不到。官方已经证明，存在一个尖锐的相变点，即可检测性阈值，低于这个阈值，所有算法肯定都无法发现隐藏结构。这一结果不仅对社区检测有指导意义，而且对更一般的网络科学也有指导意义。它告诉我们，关于互联网，有一些问题是有明确答案的，但不可能找到。
另一种量化社区检测算法性能的方法是测量它们在真实网络中恢复已知真实社区的能力。这种方法的优点是可以测试真实环境下的性能，缺点是很少确切知道真实社区，所以正确答案存在一定的歧义。
在许多情况下，人们使用某些节点属性或元数据作为真实社区的代理，但不能保证这些元数据完全对应于社区，尽管经验证据表明这两者往往是相关的。或者，人们可以利用这种相关性创建一种算法，通过将元数据知识与网络结构相结合来推断社区，而这样的算法，至少在某些研究中，似乎优于那些仅基于结构的算法。
2.5社区的重叠结构、层级结构和嵌入结构
到目前为止，我们已经关注了将网络划分为离散且不重叠的社会的经典问题，但也有一系列对其他类型结构的变化和扩展。
在社交网络和其他网络中，同一节点属于多个社区的重叠或混合成员社区是常见的。“核心-外围结构”这一术语所描述的网络可分为高密度组和低密度组，核心密集，外围稀疏，或密度不同的较大嵌套组。所有这些结构类型都可以使用模块化变量或统计模型来检测。
再远一点就是有势空结构或层的网络。这些网络具有(或可以指定)与边的位置相关的数值。分层可以看作是一个具有连续和标量社区标签的社区结构，而不是离散的分类标签。每个节点也可以有多个值，可以看作空中定位节点的坐标，边往往位于附近节点之间。这种方法叫做网络嵌入。有一系列在低维空空间中寻找网络嵌入的算法，即使事先不知道节点值，也能有效地推断出节点值。
网络嵌入算法包括经典的方法，如spring嵌入算法和Laplacian谱嵌入，这些方法最初是考虑到网络可视化而开发的，统计方法更类似于连续版的社区检测。在实践中，表达性学习方法与本综述中描述的方法有很大不同，通常采用深度学习或神经网络方法。但如果把得到的分数看作几何空中的坐标，就意味着学习可以给出和嵌入法类似的结果。除了对自身感兴趣之外，嵌入还提供了另一种检测标准离散社区的方法:在embedding 空中可以将社区定义为紧密连接的节点组，使用经典的数据聚类方法可以检测到这样的组。
3。Outlook
互联网社区发现是一个活跃的研究领域。新算法的开发继续受到极大的关注，特别是集中在提高准确性、提供正式的性能保证以及开发计算高效的方法以应用于非常大的数据集。在数学和理论计算机科学中，已经并将继续进行大量工作来限制算法性能和形式检测边界。
另一个感兴趣的领域是开发新的网络结构统计模型，该模型可用于生成基准网络、社区推理算法和其他更通用的推理算法。我们设想在测量方面取得进一步的进展，特别是基于信息论的原理，来描述关联，比较网络的替代划分，以及将划分聚类成有代表性的组。学习的进展将使我们能够使用多种数据类型进行社区检测，而不仅仅是网络结构，并为解决问题提供了一种新的强有力的方法。
最后，社区检测方法的应用令人眼花缭乱，揭示了物理、生物、工程、计算机科学、社会科学等领域的网络结构。
引用
1.纽曼，M. E. J. Networks(牛津大学出版社，2018)。
2.Fortunato，S. Phys. Rep. 486，75–174(2010)。
3.《社会网络分析:方法和应用》(剑桥大学出版社，1994年)。
4.格文和纽曼，医学工程学报。国家科学院。Sci。美国99，7821–7826(2002年)。
5.纽曼，M. E. J .和格文，M. Phys. Rev. E 69，026113 ( 2004)。
6.纽曼，M. E. J. Phys. Rev. E 69，066133 ( 2004)。
7.吉梅拉，r . Sales-Pardo，m .和Amaral，l . a . n . phys rev . E 70，
8.025101 ( R ) ( 2004年)。Blondel，V. D .，Guillaume，J.-L .，Lambiotte，r .和Lefebvre，E. J. Stat .机甲战士。2008，P10008 ( 2008)。
9.《社会网络》5，109–137(1983)。
10.佩肖托，物理博士，列特。110, 148701 ( 2013 ) .
11.罗斯韦尔，m .和博格斯特伦，C. T. Proc .国家科学院。Sci。美国105，1118–1123(2008年)。
12.Fortunato，s .和Barthelemy，M. Proc国家科学院。Sci。美国104，36–41(2007年)。
13.Reichardt，j .和Bornholdt，S. Phys. Rev. E 74，016110 ( 2006年)。
14.《佩肖托物理学报》第4版，011047页(2014年)。
15.安达信、钟、郎，计算机科学基础研讨会(FOCS ' 06 ) 2006年第47届年度IEEE 475–486(IEEE，2006)。
16.Lancichinetti，a .，Radicchi，f .，Ramasco，J. J .和Fortunato，S. PLoS ONE 6，e18961 ( 2011年)。
17.Danon，l .，Diaz-Guilera，a .，Duch，J. Arenas，A. J. Stat .机甲战士。2005年，P09008 ( 2005)。
18.艾伯特和巴拉巴西公司。物理74，47–97(2002)。
19.《医学工程物理学评论》E 83，016107 ( 2011)。
20.Lancichinetti，a .，Fortunato，s .和Radicchi，F. Phys. Rev. E 78，046110 ( 2008年)。
21.弗雷德，A. L. N .和贾恩，在进行中。2003年IEEE计算机系统芯片。糖膏剂计算机视觉模式识别128–136(IEEE，2003)。
22.Lancichinetti，a .和Fortunato，S. Phys. Rev. E 80，056117 ( 2009年)。
23.Decelle，a .，Krzakala，f .，Moore，c .和Zdeborov á，L. Phys. Rev. E 84，066106 ( 2011年)。
24.马苏里埃，在进行中。第46届美国计算机学会年会计算理论694–703(美国计算机学会，2014)。
25.莫塞尔，e。尼曼，j。和斯莱，a。可能。理论关系。字段162、431–461(2015)。
26.Hric，d .，Darst，R. K. Fortunato，S. Phys. Rev. E 90，062805 ( 2014年)。
27.纽曼，M. E. J .和克劳塞特，a .纳特。Commun。7, 11863 ( 2016 ) .
28.皮尔，l，拉勒莫尔，D. B .和克劳塞特，A. Sci。Adv. 3，e1602548 ( 2017)。
29.Clauset，a .，More，c .和Newman，M. E. J. Nature 453，98–101(2008年)。
30.帕拉，g .，德伦伊，I .，法卡什，I. 维克塞克，《自然》435，814-818(2005年)。
31.伊罗尔迪，E. M .，布莱，D. M .，芬伯格，S. E. 邢，E. P. J .马赫。学习。第9号决议，1981年至2014年(2008年)。
32.伦敦，a，吴，l-y和Uzzi，B. J. Complex Netw。1, 93 – 123 ( 2013 ) .
33.罗姆巴赫，M. P .，波特，M. A .，福勒，J. H .和穆卡，P. J .暹罗应用数学。74, 167 – 190 ( 2014 ) .
34.《基于知识的系统》。151, 78 – 94 ( 2018 ) .
35.汉密尔顿，w，应，z和莱斯科维奇，j .在进行中。第31届神经信息处理系统国际会议(NIPS ' 17)1025–1035(麻省理工学院出版社，2017)。
36.霍夫博士，拉菲里，阿埃和汉多克，硕士。统计。协会97, 1090 – 1098 ( 2002 ) .
37.纽曼，M. E. J .和佩肖托，T. P .物理评论列特。115, 088701 ( 2015 ) .
(参考资料可以通过上下滑动)查看)
高级在线读书会开始
随着对现实世界探索的深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元相互作用，而且还普遍存在许多个体同时(或按特定顺序)相互作用的现象，即高阶相互作用现象。因此，研究者开发了基于超图、单纯复形、依赖等的高级网络表示模型。，为复杂网络的分析和研究提供了新的思路。为了促进这一领域的交流与合作，我们发起了【高层在线读书会】。
Chi Chi俱乐部读书会是面向广大科研工作者的系列论文阅读活动，其目的是共同研究和探讨某一科学课题，激发科研灵感，促进科研合作。高级在线阅读俱乐部是由鲁、电子科技大学、中国地质大学三位老师联合发起的。每周分享时间为每周四19:30-21:30，预计持续10到12周。同时，我们将讨论高阶互动网络的基本概念、模型、方法和应用。本次书友会分享会将按照“基础理论”、“深度理论”、“案例分析”的模式进行。
请看:
探索复杂系统高层互动的奥秘|高层网络读书会启动
