复杂网络社团划分算法的研究与实现
|
摘要
研究发现各种复杂网络都具有社团结构,正确高效地将网络划分为合理的社团是有效地理解和利用这些网络的前提,找到网络社团划分的精确解是一个NP难题,当网络规模很大的时不存在有效精确解法。
本文提出了两种社团划分算法：第一种算法是基于遗传规律的复杂网络社团划分算法,将遗传算法应用到复杂网络社团划分的过程中,引入了可提高收敛速度的孤立点修复策略,经实验证明此算法具有在复杂网络的海量划分方案中搜索到可接受划分方案的能力；第二种算法是基于引力定律的复杂网络社团划分算法,算法中提出弹性算法的概念,将复杂网络节点邻接关系快速映射到二维空间,继而结合引力聚类方法快速识别出社团结构,经实验证明此算法在不需要较多先验信息的情况下表现出较优的划分速度和划分精度。
为辅助算法研究,本文提出了用于验证划分算法的方案,给出了利用真实数据构建复杂网络的方法,提供了随机网络生成算法,搭建了可扩展的网络社团划分算法试验平台,实现了三种对比划分算法。
It was found that networks have a feature called community structure. Partitioning those networks into rational communities correctly and efficiently is the premise of understanding and taking advantage of these networks effectively. Finding an exact solution to network community partitioning is a NP problem and there is no precise and effective solution when it comes to large network scale.
Two community partitioning algorithms were proposed in this paper:The first algorithm is a complex network community partitioning algorithm based on the genetic law. In this algorithm, the genetic algorithm was applied to the implementation process of a complex network community partitioning and an isolated point repair strategy which can enhance the convergence rate was introduced. It's proved through the experiments that this algorithm is capable of searching an acceptable partitioning scheme for a complex network from a mass of partitioning schemes. The second algorithm is based on the law of gravitation and a concept of flexible algorithm was put forward. A complex network adjacency was quickly mapped to the two-dimensional space by the flexible algorithm, after that, nodes with higher association formed a relatively dense cluster, and then the community structure could quickly be identified combined with gravitational clustering method. Experiments proved that this algorithm performs well in partitioning rate and accuracy with less priori information.
Furthermore, this paper presented a method of validating partitioning algorithms to assist the research. Two methods which can use real data to build a complex network were given and a random network generation algorithm was provided. We also built a scalable network community partitioning algorithm test platform and a comparison between three kinds of algorithms was achieved.
本文提出了两种社团划分算法：第一种算法是基于遗传规律的复杂网络社团划分算法,将遗传算法应用到复杂网络社团划分的过程中,引入了可提高收敛速度的孤立点修复策略,经实验证明此算法具有在复杂网络的海量划分方案中搜索到可接受划分方案的能力；第二种算法是基于引力定律的复杂网络社团划分算法,算法中提出弹性算法的概念,将复杂网络节点邻接关系快速映射到二维空间,继而结合引力聚类方法快速识别出社团结构,经实验证明此算法在不需要较多先验信息的情况下表现出较优的划分速度和划分精度。
为辅助算法研究,本文提出了用于验证划分算法的方案,给出了利用真实数据构建复杂网络的方法,提供了随机网络生成算法,搭建了可扩展的网络社团划分算法试验平台,实现了三种对比划分算法。
It was found that networks have a feature called community structure. Partitioning those networks into rational communities correctly and efficiently is the premise of understanding and taking advantage of these networks effectively. Finding an exact solution to network community partitioning is a NP problem and there is no precise and effective solution when it comes to large network scale.
Two community partitioning algorithms were proposed in this paper:The first algorithm is a complex network community partitioning algorithm based on the genetic law. In this algorithm, the genetic algorithm was applied to the implementation process of a complex network community partitioning and an isolated point repair strategy which can enhance the convergence rate was introduced. It's proved through the experiments that this algorithm is capable of searching an acceptable partitioning scheme for a complex network from a mass of partitioning schemes. The second algorithm is based on the law of gravitation and a concept of flexible algorithm was put forward. A complex network adjacency was quickly mapped to the two-dimensional space by the flexible algorithm, after that, nodes with higher association formed a relatively dense cluster, and then the community structure could quickly be identified combined with gravitational clustering method. Experiments proved that this algorithm performs well in partitioning rate and accuracy with less priori information.
Furthermore, this paper presented a method of validating partitioning algorithms to assist the research. Two methods which can use real data to build a complex network were given and a random network generation algorithm was provided. We also built a scalable network community partitioning algorithm test platform and a comparison between three kinds of algorithms was achieved.
引文
[1]王林,戴冠中.复杂网络中的社团发现—理论与应用[J].科技导报.2005,23(8)：62-65.
[2]S.Wasserman, K.Faust. Social Network Analysis[M].Cambridge University Press,Cambridge 1994.
[3]Fell D A, Wagner A. The small word of metabolism [J], Nature2000, (18):1 121-1 122.
[4]Wang XY Zhou AY. Linkage analysis for the World Wide Web and its application[J]:A survey. Journal of Software,2003,14(10):1768-1780.
[5]Jeong H,Tombor B,Albert R.The large-scale organization of metabolic network[J]. Nature,2000,407:651-654.
[6]J.Duch and A.Arenas, Community detection in complex. networks using extremal optimization. Phys. Rev. E 72,027104 (2005).
[7]Newman MEJ. Modularity and communities structure in networks. Proc. of the National Academy of Science,2006,103(23):8577-8582.
[8]Shi J, Malik J. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligent,2000,22(8).
[9]Garey MR, Johnson DS. Computers and Intractability:A Guide to the Theory of NP-Completeness. New York:W.H. Freeman&Co.,1990.60-63.888-904.
[10]Kernighan B W, lin S.An efficient heurisitic procedure for partitioning graphs[J].BellSystem Technical Journal,1970,49:291-307.
[11]Newman MEJ. Detecting community structure in networks. European Physical Journal (B),2004,38(2):321-330.
[12]Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E,2004,69(6):066133.
[13]Guimera R, Amaral LAN. Functional cartography of complex metabolic networks. Nature,2005,433(7028):895-900.
[14]Flake GW, Lawrence S, Giles CL, Coetzee FM. Self-Organization and identification of Web communities. IEEE Computer,2002,35(3):66-71.
[15]Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. of the National Academy of Science,2002,9(12):7821-7826.
[16]Wu F, Huberman BA. Finding communities in linear time. A physics approach. European Physical Journal B,2004,38(2):331-338.
[17]Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structures of complex networks in nature and society. Nature,2005,435(7043):814-818.
[18]Hall KM. An r-dimensional quadratic placement algorithm. Management Science, 1970,17(3):219-229.
[19]Donetti L, Munoz MA. Detecting network communities:A new systematic and efficient algorithm. Journal of Statistical Mechanics:Theory and Experiment, 2004,10:P 10012. http://www.iop.org/EJ/abstract/1742-5468/2004/10/P 10012.
[20]杨楠,弓丹志,李忺,孟小峰.Web社团发现技术综述[J].计算机研究发展.2005,42(3)：439-447.
[21]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks.cond-mat/0309488. (2004).
[22]Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E,2004,69(2):026113.
[23]R.C.Eberhart and Y. Shi, Comparison between Genetic Algorithm and Particle Swarm Optimization, Evolutionary Programming VII(1998), Lecture Notes in Computer Science 1447,611-616. Springer.
[24]旺小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社,2006.162-192.
[25]Shi, YH, Eberhart, RC, A Modified Particle Swarm Optimizer, IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, May4-9,1998.
[26]张天伍,詹自熬.一种基于引力的聚类算法.河南科学,2009,27(1)：70-73.
[27]张天伍,荆立夏.一种基于网格的引力聚类算法.微计算机信息,2009,25(6)：270-271.
[28]于勇前,赵相国,陈衡岳等.基于引力概念的聚类质量评估算法.东北大学学报,2007,28(8)：1109-1112.
[29]Zachary W. An informationflowmodel for conflict and fission in small group[J]. Journal of Anthropological Research,1977,33:452-473.
[30]王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].软件学报2003.14(10)：1768-1780.
[2]S.Wasserman, K.Faust. Social Network Analysis[M].Cambridge University Press,Cambridge 1994.
[3]Fell D A, Wagner A. The small word of metabolism [J], Nature2000, (18):1 121-1 122.
[4]Wang XY Zhou AY. Linkage analysis for the World Wide Web and its application[J]:A survey. Journal of Software,2003,14(10):1768-1780.
[5]Jeong H,Tombor B,Albert R.The large-scale organization of metabolic network[J]. Nature,2000,407:651-654.
[6]J.Duch and A.Arenas, Community detection in complex. networks using extremal optimization. Phys. Rev. E 72,027104 (2005).
[7]Newman MEJ. Modularity and communities structure in networks. Proc. of the National Academy of Science,2006,103(23):8577-8582.
[8]Shi J, Malik J. Normalized cuts and image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligent,2000,22(8).
[9]Garey MR, Johnson DS. Computers and Intractability:A Guide to the Theory of NP-Completeness. New York:W.H. Freeman&Co.,1990.60-63.888-904.
[10]Kernighan B W, lin S.An efficient heurisitic procedure for partitioning graphs[J].BellSystem Technical Journal,1970,49:291-307.
[11]Newman MEJ. Detecting community structure in networks. European Physical Journal (B),2004,38(2):321-330.
[12]Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E,2004,69(6):066133.
[13]Guimera R, Amaral LAN. Functional cartography of complex metabolic networks. Nature,2005,433(7028):895-900.
[14]Flake GW, Lawrence S, Giles CL, Coetzee FM. Self-Organization and identification of Web communities. IEEE Computer,2002,35(3):66-71.
[15]Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. of the National Academy of Science,2002,9(12):7821-7826.
[16]Wu F, Huberman BA. Finding communities in linear time. A physics approach. European Physical Journal B,2004,38(2):331-338.
[17]Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structures of complex networks in nature and society. Nature,2005,435(7043):814-818.
[18]Hall KM. An r-dimensional quadratic placement algorithm. Management Science, 1970,17(3):219-229.
[19]Donetti L, Munoz MA. Detecting network communities:A new systematic and efficient algorithm. Journal of Statistical Mechanics:Theory and Experiment, 2004,10:P 10012. http://www.iop.org/EJ/abstract/1742-5468/2004/10/P 10012.
[20]杨楠,弓丹志,李忺,孟小峰.Web社团发现技术综述[J].计算机研究发展.2005,42(3)：439-447.
[21]Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks.cond-mat/0309488. (2004).
[22]Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E,2004,69(2):026113.
[23]R.C.Eberhart and Y. Shi, Comparison between Genetic Algorithm and Particle Swarm Optimization, Evolutionary Programming VII(1998), Lecture Notes in Computer Science 1447,611-616. Springer.
[24]旺小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社,2006.162-192.
[25]Shi, YH, Eberhart, RC, A Modified Particle Swarm Optimizer, IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, May4-9,1998.
[26]张天伍,詹自熬.一种基于引力的聚类算法.河南科学,2009,27(1)：70-73.
[27]张天伍,荆立夏.一种基于网格的引力聚类算法.微计算机信息,2009,25(6)：270-271.
[28]于勇前,赵相国,陈衡岳等.基于引力概念的聚类质量评估算法.东北大学学报,2007,28(8)：1109-1112.
[29]Zachary W. An informationflowmodel for conflict and fission in small group[J]. Journal of Anthropological Research,1977,33:452-473.
[30]王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].软件学报2003.14(10)：1768-1780.