复杂网络社团结构发现算法的研究
|
摘要
复杂网络可以用来描述现实社会中的实际网络,比如Internet,交通网,电子邮件联系网,电力网等常见的实体网络。它也可以表示包含大量个体和个体之间相互作用的系统,如恒星及星际气体中的化学反应,人与人之间的社会关系,物种之间的捕食关系,科学研究中的合作关系等。人们生活在一个充满着各种各样的复杂网络的世界中。这也使得对复杂网络的研究成为必要。由于复杂网络中节点众多,结构复杂,所以研究复杂网络非常困难。然而,复杂网络的社团结构性质可以帮助了解网络结构与分析网络特性,因此寻找网络中的社团结构具有极为重要的意义。
从20世纪末开始,复杂网络的研究已渗透到生命科学、数理学科和工程学科、社会科学等众多不同的领域。对复杂网络的研究,已成为科学研究中一个极其重要的富有挑战性的课题。寻找复杂网络中的社团结构已经成为复杂网络研究的热点之一,本文正是对复杂网络中社团结构的发现方法进行研究。
本文在详细研究已有的复杂网络社团结构发现算法的基础上,提出了两种新的社团发现方法:
(1)在谱平分法的基础上,提出了一种新的复杂网络社团结构发现算法——基于谱平分法的社团划分方法。该算法对传统的SNN相似度矩阵进行改进,然后将改进后的矩阵与谱平分算法相结合来寻找网络中的社团结构。通过多个经典实例的验证,证明该方法对社团结构不明显的网络也具有较好的划分效果。并且与目前比较流行的社团发现算法进行比较可知,利用该算法划分得到的结果准确率较高。
(2)将Wu-Huberman算法和贪婪算法的思想相结合,提出了一种新的社团发现方法——基于Wu-Huberman方法和贪婪算法相结合的聚类算法。该方法定义了一种新的局部模块度计算方法,并采用了新的距离衡量标准,即斜率距离来衡量社团之间的距离。通过实例验证可知,在社团数目未知的情况下,与已有的社团发现算法相比,该方法在计算速度上也有了明显的改善。
Complex networks provide powerful tools to describe real networks in nature and society, such as the Internet, traffic system, Email communication system and cellular metabolism. They also indicate systems which include a large number of individuals interacting with each other, for instance, chemical reactions in stars and interstellar gases, the social relationships between different individuals, the food cycles in nature and the collaborations in science research. People live in the world which filled with kinds of complex networks. So it is necessary and significant to investigate the properties of complex networks. But it is difficult to study some of characteristics of complex network duo to the huge number of nodes and complicated structures in networks. The community structures in complex network are helpful to comprehend the structures of networks and analyze the specific properties of the whole network. Therefore, detection of community structure becomes very important and meaningful.
Beginning at the end of 20th century, the research of complex network has been permeating through different areas, such as life science, mathematical science, engineering science, social science and so on. It becomes a very important and challenged subject in scientific research. Detecting community structure becomes one of the most popular issues in complex networks.
Some classical detecting community structure algorithms are investigated in detail firstly, and then two new methods are proposed.
(1) Based on the spectral bisection method, the paper gives a new algorithm for detecting the community structure in complex networks——a community partitioning algorithm based on spectral bisection method. This approach improves SNN similarity matrix and combines it with spectral bisection method to find the community structure. The experiments show the validity of the method. It also proves that the method is efficient to those networks with unobvious community structure. The result obtained here is compared with other popular ones. The conclusion is that the accuracy of the results calculated by this approach is much better than the known ones.
(2) Based on Wu-Huberman method and greedy algorithm, this paper proposes a new clustering algorithm——a new clustering algorithm based on Wu-Huberman method and greedy algorithm. This method defines a new calculative formula of local modularity and a distance measure criterion named slope distance. The experiments show the validity of the algorithm. The result is that the speed calculated by this approach is much faster than the current ones.
从20世纪末开始,复杂网络的研究已渗透到生命科学、数理学科和工程学科、社会科学等众多不同的领域。对复杂网络的研究,已成为科学研究中一个极其重要的富有挑战性的课题。寻找复杂网络中的社团结构已经成为复杂网络研究的热点之一,本文正是对复杂网络中社团结构的发现方法进行研究。
本文在详细研究已有的复杂网络社团结构发现算法的基础上,提出了两种新的社团发现方法:
(1)在谱平分法的基础上,提出了一种新的复杂网络社团结构发现算法——基于谱平分法的社团划分方法。该算法对传统的SNN相似度矩阵进行改进,然后将改进后的矩阵与谱平分算法相结合来寻找网络中的社团结构。通过多个经典实例的验证,证明该方法对社团结构不明显的网络也具有较好的划分效果。并且与目前比较流行的社团发现算法进行比较可知,利用该算法划分得到的结果准确率较高。
(2)将Wu-Huberman算法和贪婪算法的思想相结合,提出了一种新的社团发现方法——基于Wu-Huberman方法和贪婪算法相结合的聚类算法。该方法定义了一种新的局部模块度计算方法,并采用了新的距离衡量标准,即斜率距离来衡量社团之间的距离。通过实例验证可知,在社团数目未知的情况下,与已有的社团发现算法相比,该方法在计算速度上也有了明显的改善。
Complex networks provide powerful tools to describe real networks in nature and society, such as the Internet, traffic system, Email communication system and cellular metabolism. They also indicate systems which include a large number of individuals interacting with each other, for instance, chemical reactions in stars and interstellar gases, the social relationships between different individuals, the food cycles in nature and the collaborations in science research. People live in the world which filled with kinds of complex networks. So it is necessary and significant to investigate the properties of complex networks. But it is difficult to study some of characteristics of complex network duo to the huge number of nodes and complicated structures in networks. The community structures in complex network are helpful to comprehend the structures of networks and analyze the specific properties of the whole network. Therefore, detection of community structure becomes very important and meaningful.
Beginning at the end of 20th century, the research of complex network has been permeating through different areas, such as life science, mathematical science, engineering science, social science and so on. It becomes a very important and challenged subject in scientific research. Detecting community structure becomes one of the most popular issues in complex networks.
Some classical detecting community structure algorithms are investigated in detail firstly, and then two new methods are proposed.
(1) Based on the spectral bisection method, the paper gives a new algorithm for detecting the community structure in complex networks——a community partitioning algorithm based on spectral bisection method. This approach improves SNN similarity matrix and combines it with spectral bisection method to find the community structure. The experiments show the validity of the method. It also proves that the method is efficient to those networks with unobvious community structure. The result obtained here is compared with other popular ones. The conclusion is that the accuracy of the results calculated by this approach is much better than the known ones.
(2) Based on Wu-Huberman method and greedy algorithm, this paper proposes a new clustering algorithm——a new clustering algorithm based on Wu-Huberman method and greedy algorithm. This method defines a new calculative formula of local modularity and a distance measure criterion named slope distance. The experiments show the validity of the algorithm. The result is that the speed calculated by this approach is much faster than the current ones.
引文
[1]汪小帆,李翔,陈关荣编著.复杂网络理论及其应用.清华大学出版社,2006
[2] Erdos P, Renyi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 1960, 5:17~60
[3] Granovetter M. The strength of weak ties. American Journal of Sociology, 1973,78(6): 1360~1380
[4] Watts D J, Strogatz S H. Collective dynamics of‘small world’networks. Nature, 1998, 393(6684): 440~442
[5] Barabasi A L, Albert R. Emergence of scaling in random networks. Science,1999, 286(5439): 509~512
[6] Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci USA,2002, 99: 7821~7826
[7] Gleiser P, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6: 565~573
[8] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49:291~307
[9] Fiedler M. Algebraic connectivity of graphs. Czech Math J, 1973, 23: 298~305
[10] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl, 1990, 11:430
[11] Scott J. Social Network Analysis: A Handbook. London: Sage Publications. 2nd ed., 2002
[12] Newman M E J. Fast algorithm for detecting community structure in networks. Proc. Natl. Acad. Sci., 2001, 99: 7821~7826
[13] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814~818
[14] Zachary W W. An information flow model for conflict and fission in small groups . Journal of Anthropological Research, 1977, 33:452~473
[15]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学,2005,2(3):1~12
[16]王林,戴冠中.复杂网络中的社区发现——理论与应用.科技导报,2005,23(8):62~66
[17]阮晓钢,李晓明,王金莲.边介数聚类算法在肿瘤基因表达谱中的应用.北京工业大学学报,2008,34(7): 696~700
[18] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69: 02611
[19] Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69: 066133
[20]谭建,喻小军.基于派系过滤算法的企业集群模块化应用研究.科技进步与对策. 2008, 25(12): 122~124
[21]谭,斯坦巴赫著;范明等译.数据挖掘导论.人民邮政出版社. 2006
[22]沈桂玲,吴谨.一种改进的模糊C-均值图像分割算法.信息技术. 2008, 12: 26~28
[23] Junhua Zhang, Shihua Zhang, Xiang-Sun Zhang. Detecting community structure in complex networks based on a measure of information discrepancy. Physica A, 2008, 387:1675~1682
[24] Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A, 2007, 374:483~490
[25] Wu F, Huberman B A. Finding communities in linear time: A physics approach. Eur. Phys. J. B , 2004, 38: 331~338
[26]卢盼,徐培德.基于贪婪算法成像侦查卫星调度方法研究.计算机仿真. 2008, 25(2): 37~40
[27] Clauset A. Finding local community structure in networks. Phys. Rev. E, 2005, 72:026132
[28]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真. 2007, 24(11): 82~85
[29] Castellano C, Cecconi F, Loreto V, Parisi, D, Radicchi F. Self-contained algorithms to detect communities in networks. Eur. Phys. J. B, 2004, 38: 311~319
[2] Erdos P, Renyi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., 1960, 5:17~60
[3] Granovetter M. The strength of weak ties. American Journal of Sociology, 1973,78(6): 1360~1380
[4] Watts D J, Strogatz S H. Collective dynamics of‘small world’networks. Nature, 1998, 393(6684): 440~442
[5] Barabasi A L, Albert R. Emergence of scaling in random networks. Science,1999, 286(5439): 509~512
[6] Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci USA,2002, 99: 7821~7826
[7] Gleiser P, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6: 565~573
[8] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49:291~307
[9] Fiedler M. Algebraic connectivity of graphs. Czech Math J, 1973, 23: 298~305
[10] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl, 1990, 11:430
[11] Scott J. Social Network Analysis: A Handbook. London: Sage Publications. 2nd ed., 2002
[12] Newman M E J. Fast algorithm for detecting community structure in networks. Proc. Natl. Acad. Sci., 2001, 99: 7821~7826
[13] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814~818
[14] Zachary W W. An information flow model for conflict and fission in small groups . Journal of Anthropological Research, 1977, 33:452~473
[15]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学,2005,2(3):1~12
[16]王林,戴冠中.复杂网络中的社区发现——理论与应用.科技导报,2005,23(8):62~66
[17]阮晓钢,李晓明,王金莲.边介数聚类算法在肿瘤基因表达谱中的应用.北京工业大学学报,2008,34(7): 696~700
[18] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69: 02611
[19] Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69: 066133
[20]谭建,喻小军.基于派系过滤算法的企业集群模块化应用研究.科技进步与对策. 2008, 25(12): 122~124
[21]谭,斯坦巴赫著;范明等译.数据挖掘导论.人民邮政出版社. 2006
[22]沈桂玲,吴谨.一种改进的模糊C-均值图像分割算法.信息技术. 2008, 12: 26~28
[23] Junhua Zhang, Shihua Zhang, Xiang-Sun Zhang. Detecting community structure in complex networks based on a measure of information discrepancy. Physica A, 2008, 387:1675~1682
[24] Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A, 2007, 374:483~490
[25] Wu F, Huberman B A. Finding communities in linear time: A physics approach. Eur. Phys. J. B , 2004, 38: 331~338
[26]卢盼,徐培德.基于贪婪算法成像侦查卫星调度方法研究.计算机仿真. 2008, 25(2): 37~40
[27] Clauset A. Finding local community structure in networks. Phys. Rev. E, 2005, 72:026132
[28]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真. 2007, 24(11): 82~85
[29] Castellano C, Cecconi F, Loreto V, Parisi, D, Radicchi F. Self-contained algorithms to detect communities in networks. Eur. Phys. J. B, 2004, 38: 311~319