We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 3
May  2012
Turn off MathJax
Article Contents
Abstract
References
Mao-Guo Gong, Ling-Jun Zhang, Jing-Jing Ma, Li-Cheng Jiao. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467. DOI: 10.1007/s11390-012-1235-y
Citation: Mao-Guo Gong, Ling-Jun Zhang, Jing-Jing Ma, Li-Cheng Jiao. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467. DOI: 10.1007/s11390-012-1235-y
shu

Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm

  • Key Lab of Intelligent Perception and Image Understanding of Ministry of Education, Xidian University Xi'an 710071, China

Funds: This work was supported by the National High Technology Research and Development 863 Program of China under Grant No. 2009AA12Z210, the Program for New Century Excellent Talents in University of China under Grant No. NCET-08-0811, the Program for New Scientific and Technological Star of Shaanxi Province of China under Grant No. 2010KJXX-03, and the Fundamental Research Funds for the Central Universities of China under Grant No. K50510020001.
More Information
  • Author Bio:

    Mao-Guo Gong received the B.Eng. degree in electronic engineer-ing and Ph.D. degree in electronic science and technology from Xidian University, Xi'an, China, in 2003 and 2009, respectively. Since 2006, he has been a teacher with Xidian Univer-sity.

  • Received Date: August 28, 2011
  • Revised Date: December 12, 2011
  • Published Date: May 04, 2012
    Abstract
  • Community structure is one of the most important properties in social networks, and community detection has received an enormous amount of attention in recent years. In dynamic networks, the communities may evolve over time so that pose more challenging tasks than in static ones. Community detection in dynamic networks is a problem which can naturally be formulated with two contradictory objectives and consequently be solved by multiobjective optimization algorithms. In this paper, a novel multiobjective immune algorithm is proposed to solve the community detection problem in dynamic networks. It employs the framework of nondominated neighbor immune algorithm to simultaneously optimize the modularity and normalized mutual information, which quantitatively measure the quality of the community partitions and temporal cost, respectively. The problem-specific knowledge is incorporated in genetic operators and local search to improve the effectiveness and efficiency of our method. Experimental studies based on four synthetic datasets and two real-world social networks demonstrate that our algorithm can not only find community structure and capture community evolution more accurately but also be more steadily than the state-of-the-art algorithms.
    • FullText(HTML)
    • References (38)
  • [1]
    Greene D, Doyle D, Cunningham P. Tracking the evolution ofcommunities in dynamic social networks. In Proc. Int. Conf.Advances in Social Networks Analysis and Mining, August2010, pp.176-183.
    [2]
    Yang T B, Chi Y, Zhu S H, Gong Y H, Jin R. Detecting com-munities and their evolutions in dynamic social networks —— aBayesian approach. Machine Learning, 2011, 82(2): 157-189.
    [3]
    Lin Y R, Chi Y, Zhu S H, Sundaram H, Tseng B L. Facetnet:A framework for analyzing communities and their evolutionsin dynamic networks. In Proc. the 17th Int. Conf. WorldWide Web, April 2008, pp.685-694.
    [4]
    Chakrabarti D, Kumar R, Tomkins A. Evolutionary cluster-ing. In Proc. the 12th ACM SIGKDD Int. Conf. KnowledgeDiscovery and Data Mining, August 2006, pp.554-560.
    [5]
    Folino F, Pizzuti C. A multiobjective and evolutionary clus-tering method for dynamic networks. In Proc. Int. Conf.Advances in Social Networks Analysis and Mining, August2010, pp.256-263.
    [6]
    Newman M E J, Girvan M. Finding and evaluating commu-nity structure in networks. Physical Review E, 2004, 69(2):026113.
    [7]
    Girvan M, Newman M E J. Community structure in socialand biological networks. Proceedings of National Academyof Sciences of the United States of America, 2002, 99(12):7821-7826.
    [8]
    Newman M E J. Fast algorithm for detecting communitystructure in networks. Physical Review E, 2004, 69(6):066133.
    [9]
    Duch J, Arenas A. Community detection in complex networksusing extremal optimization. Physical Review E, 2005, 72(2):027104.
    [10]
    Fortunato S. Community detection in graphs. Physics Re-ports, 2010, 486(3-5): 75-174.
    [11]
    Lancichinetti A, Fortunato S, Kertesz J. Detecting the over-lapping and hierarchical community structure in complex net-works. New J. Physics, 2009, 11(3): 033015.
    [12]
    Du N, Wang B, Wu B. Community detection in complex net-works. Journal of Computer Science and Technology, 2008,23(4): 672-683,
    [13]
    Kumar R, Novak J, Raghavan P, Tomkins A. On the burstyevolution of blogspace. In Proc. the 12th Int. Conf. WorldWide Web, May 2005, pp.568-576.
    [14]
    Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: Den-sification laws, shrinking diameters and possible explanations.In Proc. the 11th Int. Conf. Knowledge Discovery and DataMining, August 2005, pp.177-187.
    [15]
    Palla G, Barabasi A L, Vicsek T. Quantifying social groupevolution. Nature, 2007, 446(7136): 664-667.
    [16]
    Asur S, Parthasarathy S, Ucar D. An event-based frameworkfor characterizing the evolutionary behavior of interactiongraphs. ACM Transactions on Knowledge Discovery fromData, 2009, 3(4): Article No. 16.
    [17]
    Sarkar P, Moore A W. Dynamic social network analysis usinglatent space models. ACM SIGKDD Exploration Newsletter,2005, 7(2): 31-40.
    [18]
    Chi Y, Song X D, Zhou D, Hino K, Tseng B L. Evolutionaryspectral clustering by incorporating temporal smoothness. InProc. the 13th Int. Conf. Knowledge Discovery and DataMining, August 2007, pp.153-162.
    [19]
    Ahmed A, Xing E. Dynamic non-parametric mixture modelsand the recurrent Chinese restaurant process: With applica-tions to evolutionary clustering. In Proc. the 8th SIAM Int.Conf. Data Mining, April 2008, pp.219-230.
    [20]
    Tang L, Liu H, Zhang J, Nazeri Z. Community evolution indynamic multi-mode networks. In Proc. the 14th Int. Conf.Knowledge Discovery and Data Mining, August 2008, pp.677-685.
    [21]
    KimM S, Han J W. A particle-and-density based evolutionaryclustering method for dynamic networks. Proc. Very LargeData Base Endowment, 2009, 2(1): 622-633.
    [22]
    Kim K, McKay R, Moon B R. Multiobjective evolutionaryalgorithms for dynamic social network clustering. In Proc.the 12th Conf. Genetic and Evolutionary Computation, July2010, pp.1179-1186.
    [23]
    Zitzler E, Thiele L. Multiobjective evolutionary algorithms:A comparative case study and the strength Pareto approach.IEEE Trans. Evolutionary Computation, 1999, 3(4): 257-271.
    [24]
    Knowles J, Corne D. Approximating the non-dominated frontusing the Pareto archived evolution strategy. EvolutionaryComputation, 2000, 8(2): 149-172.
    [25]
    Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and eli-tist multiobjective genetic algorithm: NSGA-II. IEEE Trans.Evolutionary Computation, 2002, 6(2): 182-197.
    [26]
    Coello C C A, Pulido G T, Lechuga M S. Handing multipleobjectives with particle swarm optimization. IEEE Trans.Evolutionary Computation, 2004, 8(3): 256-279.
    [27]
    Zhang Q F, Zhou A M, Jin Y. RM-MEDA: A regularitymodel-based multiobjective estimation of distribution algo-rithm. IEEE Trans. Evolutionary Computation, 2008, 12(1):41-63.
    [28]
    Zhang Q F, Li H. MOEA/D: A multiobjective evolutionaryalgorithm based on decomposition. IEEE Trans. Evolution-ary Computation, 2007, 11(6): 712-731.
    [29]
    Gong M G, Jiao L C, Du H F, Bo L F. Multiobjective im-mune algorithm with nondominated neighbor-based selection.Evolutionary Computation, 2008, 16(2): 225-255.
    [30]
    Danon L, Daz-Guilera A, Duch J, Arenas A. Comparing com-munity structure identification. Journal of Statistical Me-chanics: Theory and Experiment, 2005, 2005(9): P09008.
    [31]
    Park Y J, Song M S. A genetic algorithm for clustering prob-lems. In Proc. the 3rd Conf. Genetic Programming, July1998, pp.568-575.
    [32]
    Pizzuti C. GA-Net: A genetic algorithm for community detec-tion in social networks. In Proc. the 10th Int. Conf. ParallelProblem Solving from Nature, September 2008, pp.1081-1090.
    [33]
    Cormen T H, Leiserson C E, Rivest R L, Stein C. Introductionto Algorithms (2nd edition). Cambridge: MIT Press, 2001.
    [34]
    Guimera R, Amaral L A N. Functional cartography of com-plex metabolic networks. Nature, 2005, 433(7028): 895-900.
    [35]
    Jin D, He D X, Liu D Y, Baquero C. Genetic algorithm withlocal search for community mining in complex networks. InProc. the 22nd Int. Conf. Tools with Artificial Intelligence,October 2010, pp.105-112.
    [36]
    Deb K, Goel T. A hybrid multi-objective evolutionary ap-proach to engineering shape design. In Proc. the 1st Inter-national Conference on Evolutionary Multi-Criterion Opti-mization, March 2001, pp.385-399.
    [37]
    de Nooy W, Mrvar A, Batagelj V. Exploratory Social Net-work Analysis with Pajek. New York: Cambridge UniversityPress, 2005.
    [38]
    Ye Q, Zhu T, Hu D Y, Wu B, Du N, Wang B. Cell phonemini challenge award: Social network accuracy —— Explor-ing temporal communication in mobile call graphs. In Proc.IEEE Symp. Visual Analytics Science and Technology, Oc-tober 2008, pp.207-208.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (27) PDF downloads (4315) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return