LFR算法

来自集智百科 - 伊辛模型
跳到导航 跳到搜索

兰奇基内蒂-福图纳托-拉迪奇基准测试 Lancichinetti–Fortunato–Radicchi benchmark (LFR)是一种生成基准网络 baseline network(类似于真实世界网络的人工网络)的算法。他们有一个预先已知的社区,用于比较不同的社区检测方法。[1]与其他方法相比,基准测试的优点在于它解释了节点度分布 node degree distribution社区规模分布 Community size distribution异质性[2]

算法

节点度 node degree社区规模 Community size幂律分布,但指数不同。基准测试假设节点度和社区规模都具有不同指数的幂律分布,分别为[math]\displaystyle{ \gamma }[/math][math]\displaystyle{ \beta }[/math][math]\displaystyle{ N }[/math]是节点的数量,平均度为[math]\displaystyle{ \langle k \rangle }[/math]。混合参数[math]\displaystyle{ \mu }[/math]是一个节点的相邻节点的平均比例,这些相邻节点不属于基准节点所属的任何社区。这个参数控制着社区之间的边缘比例。[3]


生成基准网络的步骤如下:

步骤1:生成一个网络,其节点遵循指数为[math]\displaystyle{ \gamma }[/math]的幂律分布,并选择分布的极值[math]\displaystyle{ k_{\min} }[/math][math]\displaystyle{ k_{\max} }[/math]来获得期望平均度[math]\displaystyle{ \langle k\rangle }[/math]
步骤2:每个节点的[math]\displaystyle{ (1 - \mu) }[/math]链接部分与同一社区的节点相同,而[math]\displaystyle{ \mu }[/math]部分与其他节点相同。
步骤3:根据指数为[math]\displaystyle{ \beta }[/math]的幂律分布生成社区规模。所有规模大小的和必须等于[math]\displaystyle{ N }[/math]。最小和最大的[math]\displaystyle{ s_{\min} }[/math][math]\displaystyle{ s_{\max} }[/math]必须满足社区的定义,这样每个非孤立的节点至少存在于一个群落中:[math]\displaystyle{ s_{\min} \gt k_{\min} }[/math][math]\displaystyle{ s_{\max} \gt k_{\max} }[/math]
步骤4:最初,没有为任何社区分配任何节点。然后,每个节点被随机分配到一个社区。只要社区内相邻节点的数量不超过社区规模,就会向社区添加一个新节点,否则就不会添加。在接下来的迭代中,无归属的节点被随机分配给某个社区。如果该社区是完备的,即规模已经用尽,必须随机选择社区中的一个节点并断开其链接。当所有社区都完备且所有节点都至少属于一个社区时停止迭代。
步骤5:对节点重新布线,保持相同的节点度,但只影响内部和外部链接,使得每个节点在社区外的链接数量约等于混合参数[math]\displaystyle{ \mu }[/math][2]

调试

考虑社区的一个不重叠分割。每次迭代中随机选择的节点的社区遵循一个[math]\displaystyle{ p(C) }[/math]分布,这个分布表示随机选择的节点来自社区[math]\displaystyle{ C }[/math]的概率。考虑同一个网络的一个分割,这个分割由一些社区搜索算法预测得出,并且具有[math]\displaystyle{ p(C_2) }[/math]分布。基准分割具有[math]\displaystyle{ p(C_1) }[/math]分布。


联合分布为[math]\displaystyle{ p(C_1, C_2) }[/math]。这两个分割的相似性可以通过归一化互信息得到。


[math]\displaystyle{ I_n = \frac{\sum_{C_1,C_2} p(C_1,C_2) \log_2 \frac{p(C_1,C_2)}{p(C_1)p(C_2)} }{\frac 1 2 H(\{p(C_1)\}) + \frac 1 2 H(\{p(C_2)\})} }[/math]


如果[math]\displaystyle{ I_n=1 }[/math]基准和检测到的分割相同,且[math]\displaystyle{ I_n=0 }[/math],那么它们彼此独立。[4]


参考文献

  1. Hua-Wei Shen (2013). "Community Structure of Complex Networks". Springer Science & Business Media. 11–12.
  2. 2.0 2.1 A. Lancichinetti, S. Fortunato, and F. Radicchi.(2008) Benchmark graphs for testing community detection algorithms. Physical Review E, 78. 模板:ArXiv
  3. Twan van Laarhoven and Elena Marchiori (2013). "Network community detection with edge classifiers trained on LFR graphs". https://www.cs.ru.nl/~elenam/paper-learning-community.pdf
  4. Barabasi, A.-L. (2014). "Network Science". Chapter 9: Communities.

编者推荐

利用强化学习寻找复杂系统的关键节点

2020年6月发表在Nature Machine Intelligence的论文,利用强化学习和图嵌入技术,提出名为 FINDER 的算法框架,显著提升了这一类问题的解决效果。该研究由国防科技大学讲师范长俊、曾利,加州大学洛杉矶分校副教授孙怡舟,哈佛医学院副研究员刘洋彧合作完成。 本视频由论文第一作者、国防科技大学系统工程学院范长俊老师主讲,介绍这篇论文的研究思路、算法结果、主要结果和未来展望。


书籍领读:随机网络

本课程中,将讲解巴拉巴西网络科学书籍的第二章随机网络。


复杂系统中的幂律分布

本课程结合实际数据和丰富的学术文献,从各方面向大家展示幂律分布——复杂系统入门必修课,其特征和意义,以及如何应用,为大家打造了体系完整的幂律分布学习框架!



本中文词条粲兰翻译,由黄秋莉审校,薄荷编辑欢迎在讨论页面留言。

本词条内容翻译自 wikipedia.org,遵守 CC3.0协议。