基于多目标优化的社团发现及系统实现
|
摘要
近年来,随着复杂网络研究的兴起,复杂网络中的社团发现备受关注。社团结构是复杂网络最重要的拓扑结构属性之一,它揭示了复杂网络的隐藏规律和行为特征。复杂网络中的社团发现对揭示网络的结构和功能之间的联系有着重要的意义。社团发现中常见的方法是优化单个目标函数,例如模块度Q。目前的大多数算法都采用了将模块度作为优化目标,进而将社团发现问题转化为优化模块度的问题。然而,这些算法大部分都有很高的复杂度,并不适合解决大规模网络问题。而另一方面,由于采用单个优化目标,这些算法都不可避免地会存在解限制的问题。
为解决上述第一个问题,本文首先提出了将遗传算法引入社团发现,产生了一种新的算法,有效解决了目前的社团发现算法效率低的问题,并通过四个实验证明了该算法的有效性。
另一方面,为解决单目标优存在的解限制问题,本文又提出了将进化多目标算法应用于社团发现。该算法同时优化两个互补的目标函数,并返回一组在这两个目标函数之间进行折中优化的非占优解。在返回的非占优解集中需要选择一个作为最优解,本文进一步提出了四个模型选择标准。相关实验分为两个部分：第一部分的实验结果表明进化多目标优化算法运行一次能够找到多个从不同角度反映社区结构的划分结果,这样有效避免了解限制。实验的第二部分,通过和其他几种社团算法比较,证明了本文提出的解模型选择标准有较高的准确度。
最后,本文提出并实现了基于进化多目标优化社团发现的原型系统。该系统的主要功能分为两部分：运行算法并将运行结果进行可视化。
In recent years, as the emergece of complex network research, the Community Detecting in complex work have been given much attention. Community structrue is one of the most important topology attributes of complex network, which reveals its hidden rules and behavioral characteristic. Detecting community structure is crucial for uncovering the links between structures and function in complex networks. The popular methods are based on optimization of a single quality function, such as modularity. Many recent algorithms use the network modularity as quality metric, which turns the Community Detection into an optimization problem. However, for one thing, these algorithms have a high computational complexity, and thus they are not suitable for a complex network with a large size. For another, recent research reveals that these methods have the resolution limit.
In order to solve the first problem, this paper first proposes a new Genetic Algorithm for Community Detection and then proves it a highly efficient algorithm via four experiments.
To solve the second problem, this paper proposes to apply a multi-objective evolutionary algorithm to detect community. The method simultaneously optimizes two complementary objectives, and returns a set of different trade-off partitions. In order to find the best solution from the set of partitions, this paper further introduces four model selection criteria to select the best solution as candidate. The related experiments can be divided into two parts. The results of the first part illustrates that, in one run, the method accurately finds the communities at different hierarchical levels, which effectively avoids the resolution limit. In the second part, the experiments also show that the model selected by these two criteria is more accurate than GN and the algorithm based on modularity optimization.
The last part of this paper is to design a prototype system for our algorithm. The main function of this system includes two parts: running the algorithm and visualizing the results.
为解决上述第一个问题,本文首先提出了将遗传算法引入社团发现,产生了一种新的算法,有效解决了目前的社团发现算法效率低的问题,并通过四个实验证明了该算法的有效性。
另一方面,为解决单目标优存在的解限制问题,本文又提出了将进化多目标算法应用于社团发现。该算法同时优化两个互补的目标函数,并返回一组在这两个目标函数之间进行折中优化的非占优解。在返回的非占优解集中需要选择一个作为最优解,本文进一步提出了四个模型选择标准。相关实验分为两个部分：第一部分的实验结果表明进化多目标优化算法运行一次能够找到多个从不同角度反映社区结构的划分结果,这样有效避免了解限制。实验的第二部分,通过和其他几种社团算法比较,证明了本文提出的解模型选择标准有较高的准确度。
最后,本文提出并实现了基于进化多目标优化社团发现的原型系统。该系统的主要功能分为两部分：运行算法并将运行结果进行可视化。
In recent years, as the emergece of complex network research, the Community Detecting in complex work have been given much attention. Community structrue is one of the most important topology attributes of complex network, which reveals its hidden rules and behavioral characteristic. Detecting community structure is crucial for uncovering the links between structures and function in complex networks. The popular methods are based on optimization of a single quality function, such as modularity. Many recent algorithms use the network modularity as quality metric, which turns the Community Detection into an optimization problem. However, for one thing, these algorithms have a high computational complexity, and thus they are not suitable for a complex network with a large size. For another, recent research reveals that these methods have the resolution limit.
In order to solve the first problem, this paper first proposes a new Genetic Algorithm for Community Detection and then proves it a highly efficient algorithm via four experiments.
To solve the second problem, this paper proposes to apply a multi-objective evolutionary algorithm to detect community. The method simultaneously optimizes two complementary objectives, and returns a set of different trade-off partitions. In order to find the best solution from the set of partitions, this paper further introduces four model selection criteria to select the best solution as candidate. The related experiments can be divided into two parts. The results of the first part illustrates that, in one run, the method accurately finds the communities at different hierarchical levels, which effectively avoids the resolution limit. In the second part, the experiments also show that the model selected by these two criteria is more accurate than GN and the algorithm based on modularity optimization.
The last part of this paper is to design a prototype system for our algorithm. The main function of this system includes two parts: running the algorithm and visualizing the results.
引文
[1]Newman, M.E.J., The structure and function of complex network, in SIAM Review,45 (2003) p.167-256.
[2]Barabasi A.L., Albert R., Emergence of scaling in random networks, in Science. 1999:Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA. p.509--512.
[3]Watts D.J., Strogatz S.H., Collective Dynamics of Small-World Networks, in Nature.1998. p.440-442.
[4]Song, C., Havlin S., and H.A. Makse, Self-similarity of complex networks. Nature,2005(433):p.392-395.
[5]Boccaletti, S., et al., Complex networks:Structure and dynamics. Physics Reports,2005(424):p.175-308.
[6]Wang, X.F. and Chen G.R., Complex networks:small-world, scale-free and beyond. Circuits and Systems Magazine, IEEE,2003.3(1):p.6-20.
[7]Scott, J., Social Network Analysis. A Handbook (London, Sage Publications 2002).
[8]Guimara R. and Amaral L.A.N, Functional Cartography of Complex Metabolic Networks. Nature,2005,433:895-900.
[9]Palla G., Dereyi I., Farkas I.,et al, Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature,2005,435(7043): 814-818.
[10]Milo, R., Itzkovitz, S., et al., Network Motifs:Simple Building Blocks of Complex Networks. Science, Vol-298:824-827.
[11]Newman M.E.J., Girvan M.:Finding and Evaluating Community Structure in Networks. Physics Review E,2004 69:026113.
[12]Newman M.E.J., Fast algorithm for detecting community structure in networks. Physical review E 69 (2004) 066133.
[13]Fortunato S and Barthelemy M., Resolution Limit in Community Detection. Proceedings of the National Academy of Sciences,2007,104(1).
[14]Reichardt J. and Bornholdt S., Statistical Mechanics of Community Detection. Physics Review E,74(1):016110,2006.
[15]Arenas A., Fernandez A., Gomez S.:Multiple Resolution of Modular Structure of Complex Networks. arXiv:physics/0703218v1,2007.
[16]Kumpula J.M., Saramaki J., Kaski K., et al., Limit Resolution and Multiresolution Models in Complex Network Community Detection. arXiv:0706. 2230v2,25 Jan 2008.
[17]Brandes U., Delling D., Gaetler M., et al, On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering,2008,20(2):172-188.
[18]Cai Z.X, Xu G.Y. Artificial Intelligence Principles and Applications. Tsinghua University Press,2007.
[19]Deb K., Multiobjective Optimization using Evolutionary Algorithms. U.K: Wiley,2001.
[20]Gong M.G., Jiao L.C., Yang D.D et al, Research on Evolutionary Multi-Objective Optimization Algorithms. Journal of Software,2009,20(2): 271-289.
[21]Newman M.E.J., Detecting community structure in networks The European Physical Journal B-Condensed Matter,2004.38(2):p.321-330.
[22]Li X, Wang X F, Feed back control of scale-free coupled Henon maps. Proceeding of the Eighth International Conference on Control, Automation, Robotics and Vision (ICARCV) at Kunming, China,2004,574-578.
[23]Li X, Wang X F, Chen G, Pinning a complex dynamic network to its equilibrium. IEEE Trans. On Circuits and Systems-1,2004,61:2074-2078.
[24]Hu G., Yang J. Z, Liu W. J., Instability and controllability of linearly coupled oscillators:eigenvalue analysis. Phys. Rev. E,200,62(3):4440-4447.
[25]Hu G, Xiao J. H., Gao J. H., et al. Analytic study of satiotemoral chaos control by applying local injection.. Phys. Rev. E,2000,62(3):3043-3047.
[26]Arenas A., Diaz-Guiler A., Perez-Vicente C. J., Synchronization Reveals Topological Scales in Complex Networks. Physics Review Letter,96 114102, 2006.
[27]Tasgin M. and Bingol H.:Community Detection in Complex Networks using Genetic Algorithm, arXiv:cond-mat/0604419,2006.
[28]Duch, J., Arenas, A., Community Detection in Complex Networks using Extremal Optimization. arXiv:cond-mat/0501368,2005.
[29]Yang B., Liu D.Y., Liu J.M., et al, Complex Network Clustering Algorithm. Journal of Software,2009,20(1):54-66.
[30]Yang N., Lin S.X., Gao Q, et al, Discovering Signature of Potential Web Community from Cluster of MCL. Chinese Journal of Computers,2007, 30(7):1086-1093.
[31]Shen H.W., Chen X.Q., Chen H.Q., et al, Information Bottleneck Based Community Detection in Network. Chinese Journal of Computers,2008,31(4): 67-686.
[32]Deb K., Pratab A., Agarwal S.,et al., A fast and Elitist multi-objective genetic algorithm:NSGA-II. IEEE Trans. Evol. Comput., Vol.6, pp:182-197, Apr.2002.
[33]Veldhuizen D.A.Van, Lamont G.B., Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evol. Comput., vol.18, no.2, pp.125-147,2000.
[34]Jensen M.T., Reducing the Run-Time complexity of Multi-objective EAs:The NSGA-Ⅱ and Other Algorithms. IEEE Trans. Evol. Comput., vol.7, no.5, pp.503-515,2003.
[35]Shi C., Li Q.Y., Shi Z.Z., A Quick Multi-objective Evolutionary Algorithm Based on Dominating Tree, Journal of Software,2007,18(3):505-516.
[36]Park Y.J., Song M.S.:A Genetic Algorithm for Clustering Problem. In:Proc. 3rd Annual Conf. Genetic Program,1998:568-575.
[37]Girvan, M. and Newman, M.E.J., Community structure in social and biological net-works, PNAS 99 (2002) 7821-7826.
[38]Danon L., Diaaz-Guilera A., Duch J., et al, Comparing Community Structure Identification. Journal of Statistical Mechanics:Theory and Experiments,9,2005.
[39]http://www-personal.umich.edu/～mejn/netdata
[40]Radicchi,F., Castellano, C., Cecconi, F.,et al, Defining and Identifying Communities in Networks. PNAS, vol-101:2658.
[41]Wang X.F., Li X., Chen G.R., The Theory and Application of Complex Network. Tsinghua University Press,2006.
[42]Rosvall M., Bergstrom C.T., An information-theoretic framework for resolving community structure in complex networks. PNAS 2007,104,7327-7331.
[43]Pizzuti C., GA-Net, A Genetic Algorithm for Community Detection in Social Networks, in PPSN2008, pp.1081-1090.
[44]Pizzuti C., Community Detection in Social Networks with Genetic Algorithms, in GECCO'08.
[45]Handle J., Knowles J., An Evolutionary Approach to Multi-objective Clustering, Transaction on Evolutionary Computation, vol.11 no.1,2007.
[46]http://jung.sourceforge/net
[47]http://www.jfree.org/jfreechart/
[2]Barabasi A.L., Albert R., Emergence of scaling in random networks, in Science. 1999:Department of Physics, University of Notre Dame, Notre Dame, IN 46556, USA. p.509--512.
[3]Watts D.J., Strogatz S.H., Collective Dynamics of Small-World Networks, in Nature.1998. p.440-442.
[4]Song, C., Havlin S., and H.A. Makse, Self-similarity of complex networks. Nature,2005(433):p.392-395.
[5]Boccaletti, S., et al., Complex networks:Structure and dynamics. Physics Reports,2005(424):p.175-308.
[6]Wang, X.F. and Chen G.R., Complex networks:small-world, scale-free and beyond. Circuits and Systems Magazine, IEEE,2003.3(1):p.6-20.
[7]Scott, J., Social Network Analysis. A Handbook (London, Sage Publications 2002).
[8]Guimara R. and Amaral L.A.N, Functional Cartography of Complex Metabolic Networks. Nature,2005,433:895-900.
[9]Palla G., Dereyi I., Farkas I.,et al, Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature,2005,435(7043): 814-818.
[10]Milo, R., Itzkovitz, S., et al., Network Motifs:Simple Building Blocks of Complex Networks. Science, Vol-298:824-827.
[11]Newman M.E.J., Girvan M.:Finding and Evaluating Community Structure in Networks. Physics Review E,2004 69:026113.
[12]Newman M.E.J., Fast algorithm for detecting community structure in networks. Physical review E 69 (2004) 066133.
[13]Fortunato S and Barthelemy M., Resolution Limit in Community Detection. Proceedings of the National Academy of Sciences,2007,104(1).
[14]Reichardt J. and Bornholdt S., Statistical Mechanics of Community Detection. Physics Review E,74(1):016110,2006.
[15]Arenas A., Fernandez A., Gomez S.:Multiple Resolution of Modular Structure of Complex Networks. arXiv:physics/0703218v1,2007.
[16]Kumpula J.M., Saramaki J., Kaski K., et al., Limit Resolution and Multiresolution Models in Complex Network Community Detection. arXiv:0706. 2230v2,25 Jan 2008.
[17]Brandes U., Delling D., Gaetler M., et al, On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering,2008,20(2):172-188.
[18]Cai Z.X, Xu G.Y. Artificial Intelligence Principles and Applications. Tsinghua University Press,2007.
[19]Deb K., Multiobjective Optimization using Evolutionary Algorithms. U.K: Wiley,2001.
[20]Gong M.G., Jiao L.C., Yang D.D et al, Research on Evolutionary Multi-Objective Optimization Algorithms. Journal of Software,2009,20(2): 271-289.
[21]Newman M.E.J., Detecting community structure in networks The European Physical Journal B-Condensed Matter,2004.38(2):p.321-330.
[22]Li X, Wang X F, Feed back control of scale-free coupled Henon maps. Proceeding of the Eighth International Conference on Control, Automation, Robotics and Vision (ICARCV) at Kunming, China,2004,574-578.
[23]Li X, Wang X F, Chen G, Pinning a complex dynamic network to its equilibrium. IEEE Trans. On Circuits and Systems-1,2004,61:2074-2078.
[24]Hu G., Yang J. Z, Liu W. J., Instability and controllability of linearly coupled oscillators:eigenvalue analysis. Phys. Rev. E,200,62(3):4440-4447.
[25]Hu G, Xiao J. H., Gao J. H., et al. Analytic study of satiotemoral chaos control by applying local injection.. Phys. Rev. E,2000,62(3):3043-3047.
[26]Arenas A., Diaz-Guiler A., Perez-Vicente C. J., Synchronization Reveals Topological Scales in Complex Networks. Physics Review Letter,96 114102, 2006.
[27]Tasgin M. and Bingol H.:Community Detection in Complex Networks using Genetic Algorithm, arXiv:cond-mat/0604419,2006.
[28]Duch, J., Arenas, A., Community Detection in Complex Networks using Extremal Optimization. arXiv:cond-mat/0501368,2005.
[29]Yang B., Liu D.Y., Liu J.M., et al, Complex Network Clustering Algorithm. Journal of Software,2009,20(1):54-66.
[30]Yang N., Lin S.X., Gao Q, et al, Discovering Signature of Potential Web Community from Cluster of MCL. Chinese Journal of Computers,2007, 30(7):1086-1093.
[31]Shen H.W., Chen X.Q., Chen H.Q., et al, Information Bottleneck Based Community Detection in Network. Chinese Journal of Computers,2008,31(4): 67-686.
[32]Deb K., Pratab A., Agarwal S.,et al., A fast and Elitist multi-objective genetic algorithm:NSGA-II. IEEE Trans. Evol. Comput., Vol.6, pp:182-197, Apr.2002.
[33]Veldhuizen D.A.Van, Lamont G.B., Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art. Evol. Comput., vol.18, no.2, pp.125-147,2000.
[34]Jensen M.T., Reducing the Run-Time complexity of Multi-objective EAs:The NSGA-Ⅱ and Other Algorithms. IEEE Trans. Evol. Comput., vol.7, no.5, pp.503-515,2003.
[35]Shi C., Li Q.Y., Shi Z.Z., A Quick Multi-objective Evolutionary Algorithm Based on Dominating Tree, Journal of Software,2007,18(3):505-516.
[36]Park Y.J., Song M.S.:A Genetic Algorithm for Clustering Problem. In:Proc. 3rd Annual Conf. Genetic Program,1998:568-575.
[37]Girvan, M. and Newman, M.E.J., Community structure in social and biological net-works, PNAS 99 (2002) 7821-7826.
[38]Danon L., Diaaz-Guilera A., Duch J., et al, Comparing Community Structure Identification. Journal of Statistical Mechanics:Theory and Experiments,9,2005.
[39]http://www-personal.umich.edu/～mejn/netdata
[40]Radicchi,F., Castellano, C., Cecconi, F.,et al, Defining and Identifying Communities in Networks. PNAS, vol-101:2658.
[41]Wang X.F., Li X., Chen G.R., The Theory and Application of Complex Network. Tsinghua University Press,2006.
[42]Rosvall M., Bergstrom C.T., An information-theoretic framework for resolving community structure in complex networks. PNAS 2007,104,7327-7331.
[43]Pizzuti C., GA-Net, A Genetic Algorithm for Community Detection in Social Networks, in PPSN2008, pp.1081-1090.
[44]Pizzuti C., Community Detection in Social Networks with Genetic Algorithms, in GECCO'08.
[45]Handle J., Knowles J., An Evolutionary Approach to Multi-objective Clustering, Transaction on Evolutionary Computation, vol.11 no.1,2007.
[46]http://jung.sourceforge/net
[47]http://www.jfree.org/jfreechart/