论文部分内容阅读
摘要：复杂网络社区发现目前已成为计算机科学、生物学、社会学等多个领域研究热点之一。为快速准确地发现大规模网络中社区结构，该文提出一种基于中心节点覆盖的社区发现算法。算法以拥有最多邻居节点的中心节点开始，依次找到能覆盖整个网络节点的最少中心节点，然后以这些中心节点作为小社区，计算相交小社区间合并度量分值，每次合并两个具有最大合并度量分值的小社区，并以模块性Q值作为全局最优合并序列评价函数，全局最大Q的合并序列，即为最优社区划分结构。实验结果表明，算法对网络社区结构划分的时间复杂度为nlogn（n为网络节点数目）并具有较高准确率。
关键词：社区发现；中心节点；社区合并度量
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）04-0019-04
Abstract： Complex network community discovery has become one of the hot issues in many fields， including computer science， biology， sociology， etc. In order to quickly and accurately find the community structure of large-scale network， this paper presents a discovery algorithm based on center node whose neighbors node can cover the whole network . The algorithm starts with the most central node whose neighbor nodes can cover entire network then define them as initial small communities， then calculate the combining measure scores between these cross communities pair， each time we will merge a pair of cross communities which get the most combining measure score， and modularity Q value as a global optimal evaluation function for the merge sequence， one merge sequence which achieve maximum Q is the optimal community structure partition of the network. As described， the algorithm can even divided into a dense network into communities with approximately linear time complexity .Applying the algorithm on several typical community social networks shows that the algorithm is of great accuracy and low time complexity.
Key words： community detect； core nodes； community combining measure
1 概述
现实世界中许多复杂系统都可以被直接或转化为复杂网络表示。复杂网络一般存在一些统计特性，如“无标度”[1]，“小世界效应”[2]，“社区结构特性”[3]。现在，复杂网络中社区结构发现已经成为计算机科学、生物学、物理学、社会学等领域研究热点之一。例如生物学中蛋白质网络里同一社区内蛋白质往往具有相同功能，社会网络中同一社区范围内的所有个体具有相同行为特征，万维网网络中同一社区内网页属于同一主题或同一关键词相关等。复杂网络社区发现目的就是探测并展示这些复杂网络中固有的社区结构。
自复杂网络中社区发现问题提出至今，各领域学者专家已经提出多种发现算法。2004年Girvan和Newman提出了一个用于刻画网络社区结构优劣的量化标准模块性函数Q[4]，并启发其他学者提出基于模块性函数Q的一系列新算法[5-8]，但是该系列算法过程复杂，时间复杂度也较高；2007年Raghavan U N等针对大规模社交网络提出了标签传播算法（LPA）[9]，该算法可以在5步之内使得95%以上节点标签达到稳定状态并且适用于超大规模网络，后续有Leung[10]，Barber[11]，liu[12]等对标签传播进行一系列优化和扩展，但LPA算法的弱点是容易陷入局部最优解同时最终结果对节点更新顺序敏感，算法的准确率有待提升；而国内近年的研究如刘大有[13]，何东晓[14]等主要集中在运用蚁群算法和遗传算法结合马尔科夫随机游走或模块性函数Q来产生网络社区结构划分。
本文提出一种基于中心节点覆盖的社区发现算法。算法以拥有最多邻居节点的中心节点开始，依次找到能覆盖整个网络节点的最少中心节点，然后以这些中心节点作为小社区，计算相交小社区间合并度量分值，每次合并两个具有最大合并度量分值的小社区，并以模块性Q值作为全局最优合并序序列评价函数，全局最大Q的合并序列即为最优社区划分结构。
4 结论及展望
本算法思路简洁，不同于Vincent D Blondel等[16]提出了以多步骤计算Q值作为起始和最终划分凭据方法，提出基于拥有最多邻居节点的初始中心方法，创新性地定义了社区合并置信度度量方法，最后以模块性函数均值Q作为优化函数获取最优划分结果。不仅在小规模网络中划分准确，而且由于算法时间复杂度低可以适用于大规模网络数据。 1） 在小规模网络中划分结果准确。如在空手道网络中的社区结构划分完全正确，在海豚网络社区结构划分只误划分了两个节点。
2） 在大规模网络中应用。算法最耗时间步骤仅仅在于起始时按照节点邻居数量排序，且时间复杂度为O（nlogn），其他步骤均为线性时间复杂度，第二步直接大幅度缩减了计算量。这使得算法具有应用在大规模网络中的可行性。
3） 存在的问题。本算法在两个小数据集空手道数据和海豚网络数据集中并没有以取模块性函数Q，而是取其均值作为目标优化函数，得到较为准确地划分结果，与目前大部分论文不同。而在大网络数据集如科学家协作网络中直接以模块性函数Q作为评价函数，此时我们发现网络中社区数量较大时，模块性函数Q≈1，这也即模块性函数Q的分辨率极限问题[17]。
4） 展望。从算法流程可以看出，算法第三步小社区之间存在交集，本算法在处理时需要对交叉节点进行二次划分，这在一定程度上增加了算法的时间消耗，同时也给其创造了另外一种可能，也即划分重叠社区的可能。今后将继续改进算法并根据网络规模确定划分网络社区结构的时使用平均模块性函数Q’与直接模块性函数Q，同时尝试将改进算法使其能够运用在重叠社区发现研究中。
参考文献：
[1] Barabási A-L，Albert R.Emergence of scaling in random networks[J].Science，1999， 286（5439）： 509-512.
[2] Watts D J，Strogatz S H.Collective dynamics of small-world networks[J]. Nature， 1998， 393（6638）： 440-442.
[3] Girvan M，Newman M E J.Community structure in social and biological networks[J]. Proceedings of National Academy ofScience，2002，9（12）：7821-7826.
[4] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）： 026113.
[5] Newman M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E， 2004， 69（6）： 066133.
[6] Guimera R，Amaral L A N.Functional cartography of complex metabolic networks[J].Nature， 2005， 433（7028）： 895-900.
[7] Newman M E J. Modularity and community structure in networks[J]. Proceedings of National Academy of Science， 2006，103（23）： 8577-8582.
[8] 金弟，刘大有，杨博，等.基于局部探测的快速复杂网络聚类算法[J].电子学报，2011， 39（11）：2540-2546.
[9] Raghavan U N，Albert R，Kumara S.Near linear-time algorithm to detect community structures in large-scale networks[J].Physical Review E， 2007，76（3）： 036106.
[10] Leung I X Y，Hui P，Li`o P，et al.Towards real time community detection in large networks[J].Physical Review E，2009，79（6）：066107.
[11] Barber M J， Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E， 2009，80（2）：026129.
[12] 金弟，杨博，刘杰，等.复杂网络簇结构探测—基于随机游走的蚁群算法[J].软件学报，2012， 23（3）：451-464.
[13] 何东晓，周栩，王佐，等.复杂网络社区挖掘——基于聚类融合的遗传算法[J].自动化学报， 2010，36（8）： 1160-1170.
[14] Zachary W W.An information flow model for conflict andfission in small groups[J].Journal of Anthropological Research， 1977， 33（4）：452-473.
[15] Lusseau D.The emergent properties of a dolphin social network. Proceedings of the Royal Society B： Biological Sciences， 2003，270（Supplement 2）： S186?S188.
[16] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J]. Journal of StatisticalMechanics：Theory and Experiment，2008.
[17] Fortunato S， Barthélemy M. Resolution limit in community detection[J]. Proceedings of National Academy of Science， 2007，104（1）：36-41.
关键词：社区发现；中心节点；社区合并度量
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）04-0019-04
Abstract： Complex network community discovery has become one of the hot issues in many fields， including computer science， biology， sociology， etc. In order to quickly and accurately find the community structure of large-scale network， this paper presents a discovery algorithm based on center node whose neighbors node can cover the whole network . The algorithm starts with the most central node whose neighbor nodes can cover entire network then define them as initial small communities， then calculate the combining measure scores between these cross communities pair， each time we will merge a pair of cross communities which get the most combining measure score， and modularity Q value as a global optimal evaluation function for the merge sequence， one merge sequence which achieve maximum Q is the optimal community structure partition of the network. As described， the algorithm can even divided into a dense network into communities with approximately linear time complexity .Applying the algorithm on several typical community social networks shows that the algorithm is of great accuracy and low time complexity.
Key words： community detect； core nodes； community combining measure
1 概述
现实世界中许多复杂系统都可以被直接或转化为复杂网络表示。复杂网络一般存在一些统计特性，如“无标度”[1]，“小世界效应”[2]，“社区结构特性”[3]。现在，复杂网络中社区结构发现已经成为计算机科学、生物学、物理学、社会学等领域研究热点之一。例如生物学中蛋白质网络里同一社区内蛋白质往往具有相同功能，社会网络中同一社区范围内的所有个体具有相同行为特征，万维网网络中同一社区内网页属于同一主题或同一关键词相关等。复杂网络社区发现目的就是探测并展示这些复杂网络中固有的社区结构。
自复杂网络中社区发现问题提出至今，各领域学者专家已经提出多种发现算法。2004年Girvan和Newman提出了一个用于刻画网络社区结构优劣的量化标准模块性函数Q[4]，并启发其他学者提出基于模块性函数Q的一系列新算法[5-8]，但是该系列算法过程复杂，时间复杂度也较高；2007年Raghavan U N等针对大规模社交网络提出了标签传播算法（LPA）[9]，该算法可以在5步之内使得95%以上节点标签达到稳定状态并且适用于超大规模网络，后续有Leung[10]，Barber[11]，liu[12]等对标签传播进行一系列优化和扩展，但LPA算法的弱点是容易陷入局部最优解同时最终结果对节点更新顺序敏感，算法的准确率有待提升；而国内近年的研究如刘大有[13]，何东晓[14]等主要集中在运用蚁群算法和遗传算法结合马尔科夫随机游走或模块性函数Q来产生网络社区结构划分。
本文提出一种基于中心节点覆盖的社区发现算法。算法以拥有最多邻居节点的中心节点开始，依次找到能覆盖整个网络节点的最少中心节点，然后以这些中心节点作为小社区，计算相交小社区间合并度量分值，每次合并两个具有最大合并度量分值的小社区，并以模块性Q值作为全局最优合并序序列评价函数，全局最大Q的合并序列即为最优社区划分结构。
4 结论及展望
本算法思路简洁，不同于Vincent D Blondel等[16]提出了以多步骤计算Q值作为起始和最终划分凭据方法，提出基于拥有最多邻居节点的初始中心方法，创新性地定义了社区合并置信度度量方法，最后以模块性函数均值Q作为优化函数获取最优划分结果。不仅在小规模网络中划分准确，而且由于算法时间复杂度低可以适用于大规模网络数据。 1） 在小规模网络中划分结果准确。如在空手道网络中的社区结构划分完全正确，在海豚网络社区结构划分只误划分了两个节点。
2） 在大规模网络中应用。算法最耗时间步骤仅仅在于起始时按照节点邻居数量排序，且时间复杂度为O（nlogn），其他步骤均为线性时间复杂度，第二步直接大幅度缩减了计算量。这使得算法具有应用在大规模网络中的可行性。
3） 存在的问题。本算法在两个小数据集空手道数据和海豚网络数据集中并没有以取模块性函数Q，而是取其均值作为目标优化函数，得到较为准确地划分结果，与目前大部分论文不同。而在大网络数据集如科学家协作网络中直接以模块性函数Q作为评价函数，此时我们发现网络中社区数量较大时，模块性函数Q≈1，这也即模块性函数Q的分辨率极限问题[17]。
4） 展望。从算法流程可以看出，算法第三步小社区之间存在交集，本算法在处理时需要对交叉节点进行二次划分，这在一定程度上增加了算法的时间消耗，同时也给其创造了另外一种可能，也即划分重叠社区的可能。今后将继续改进算法并根据网络规模确定划分网络社区结构的时使用平均模块性函数Q’与直接模块性函数Q，同时尝试将改进算法使其能够运用在重叠社区发现研究中。
参考文献：
[1] Barabási A-L，Albert R.Emergence of scaling in random networks[J].Science，1999， 286（5439）： 509-512.
[2] Watts D J，Strogatz S H.Collective dynamics of small-world networks[J]. Nature， 1998， 393（6638）： 440-442.
[3] Girvan M，Newman M E J.Community structure in social and biological networks[J]. Proceedings of National Academy ofScience，2002，9（12）：7821-7826.
[4] Newman M E J，Girvan M.Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）： 026113.
[5] Newman M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E， 2004， 69（6）： 066133.
[6] Guimera R，Amaral L A N.Functional cartography of complex metabolic networks[J].Nature， 2005， 433（7028）： 895-900.
[7] Newman M E J. Modularity and community structure in networks[J]. Proceedings of National Academy of Science， 2006，103（23）： 8577-8582.
[8] 金弟，刘大有，杨博，等.基于局部探测的快速复杂网络聚类算法[J].电子学报，2011， 39（11）：2540-2546.
[9] Raghavan U N，Albert R，Kumara S.Near linear-time algorithm to detect community structures in large-scale networks[J].Physical Review E， 2007，76（3）： 036106.
[10] Leung I X Y，Hui P，Li`o P，et al.Towards real time community detection in large networks[J].Physical Review E，2009，79（6）：066107.
[11] Barber M J， Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E， 2009，80（2）：026129.
[12] 金弟，杨博，刘杰，等.复杂网络簇结构探测—基于随机游走的蚁群算法[J].软件学报，2012， 23（3）：451-464.
[13] 何东晓，周栩，王佐，等.复杂网络社区挖掘——基于聚类融合的遗传算法[J].自动化学报， 2010，36（8）： 1160-1170.
[14] Zachary W W.An information flow model for conflict andfission in small groups[J].Journal of Anthropological Research， 1977， 33（4）：452-473.
[15] Lusseau D.The emergent properties of a dolphin social network. Proceedings of the Royal Society B： Biological Sciences， 2003，270（Supplement 2）： S186?S188.
[16] Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of communities in large networks[J]. Journal of StatisticalMechanics：Theory and Experiment，2008.
[17] Fortunato S， Barthélemy M. Resolution limit in community detection[J]. Proceedings of National Academy of Science， 2007，104（1）：36-41.