运筹学在复杂网络社团结构分析中的应用

摘要/Abstract

摘要： 社团结构研究是复杂网络这一前沿领域中的重要问题,同运筹学有着密切的关联。本文介绍了传统社团结构问题的基本定义,以及最近十年通过应用运筹学理论对该问题的研究进展。这些进展包括启发式模型,到随后的概率优化模型,以及组合优化模型。通过这些介绍,说明了运筹学方法论和基本工具在复杂系统研究中所起到的重要作用。

关键词: 复杂网络, 社团结构, 运筹学, 启发式模型, 概率优化模型, 组合优化模型

Abstract: Community Structure Analysis is one of the popular research problems in the complex network study, which has closed relationship with Operation Research theory and algorithm. This paper introduces the basic definition of the community stucture problem and surveys the development of methods finding the community structure in recent ten years, especially those using OR methodology such as heuristic models, stochastic optimization models and combinatoric models. From the survey, one can see that OR methodolgy takes very important roles in the complex network study.

Key words: complex network, community structure, Operation Research, heuristic model, stochastic optimization model, combinatoric model

中图分类号:

O221

章祥荪. 运筹学在复杂网络社团结构分析中的应用[J]. 运筹与管理, 2013, 22(5): 1-11.

ZHANG Xiang-sun. Operations Research Methodology in Community Structure Analysis of Complex Networks[J]. Operations Research and Management Science, 2013, 22(5): 1-11.

参考文献

[1] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveale multiscal complexity in networks[J]. Neture Letters, 466: 761-764, 2010.
[2] Airoldi E M, Blei D M, Fienberg S E, Xing E P. Mixed membership stochastic blockmodels[J]. Journal of Machine Learning Research, 9: 1981-2014, 2008.
[3] Alderson A L. Catching the“network science”bug: insight and opportunity for operations researcher[J]. Operations Research, 56(5): 1047-1065, 2008.
[4] Barabási A L, Albert R. Emergence of scaling in rendom networks[J]. Science, 286:509, 1999.
[5] Barabási A L. The network takeover[J]. Nature Physics, 8(1): 14-16, 2012.
[6] Bickel P J, Chen A. Anonparametric view of network models and Newman-girvan and other modularities[J]. Proc. Natl. Acad. Sci. USA, 106, 201668- 21073, 2009.
[7] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks, Nature, 453, 98-101, 2008.
[8] Decelle A, Krzakala F, Moore C. Zdeborova A. Inference and phase transitions in the detection of modules in sparse networks, Phys. Rev. Lett, 107, article number 065701, 2011.
[9] Eisner U, Graph partitioning-a survey, Technical Report, 97-27, Technische Universit^..at Chemnitz, 1997.
[10] Fjällström P O. Algorithms for graph partitioning: A survey, linköping Electronic Articles in Computer and Information science 3, article number 10, 1998.
[11] Fortunato S. Community detection in graphs, physics reports, 486(3), 75-174, 2010.
[12] Fortunato S, Barthélemy M. Resolution limit in community detection, Proc. Natl. Acad. Sci. USA, 104(1), 36-41, 2007
[13] Gao Z, Lu Z, Chen W, Zhong J, Bi Y. The maximum community partition problem in networks, International Conference on Social Intelligence and Technology, 2013.
[14] Girvan M, Newman M E J. Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 7821-7826, 2002.
[15] Gleiser P, Danon L. Community structure in Jazz, Adv. Complex Syst., 6, 565, 2003.
[16] Guimerà R, Luis A, Nunes amaral, Functional cartography of complex metabolic networks, Nature, 433, 895-900, 2005.
[17] Guimeràd R S, Mossa A Tirtschi A, Amaral L A N. The worldwide air transportation network: Anomalous centrality, community structure, and c-ities'global roles, Proc. Nat1. Acad. Sci. USA, 102(22): 7794-7799, 2005.
[18] Hu Y, Chen H, Zhang P, Li M, Di Z, Fan Y. Comparative definition of community and corresponding identifying algorithm, Phys, Rev E, 78, 026121, 2008.
[19] Karrer B, Newman M E J. Stochastic blockmodels and community struc-ture in networks, Phys. Rev. E, 83, 016107, 2011.
[20] Krapivsky P L, Redner S, Leyvraz F. Connectivity of growing random networks, Phys. Rev., Lett, 85, 4629. 4632, 2000.
[21] Kullmann L, Kertesz J. Preferencial growth: exact solution of the time dependent distributions, ar Xiv: cond-mat/0012410, 2000.
[22] Li H J(李慧嘉), Wang Y(王勇), Wu L Y(吴凌云), Zhang J H(张俊华), Zhang X S(章祥荪). Potts model based on a Markov process cornputation solves the community structure problem effectively, Physical Review E 86, 016109, 2012.
[23] Li H J(李慧嘉), Wang Y(王勇), Wu L Y(吴凌云), Liu Z P(刘治平), Chen L N(陈洛南), Zhang X S(章祥荪). Community structure detection based on potts model and network's spectral characterization, Eu-rophysics Letters, 97: 48005, 2012.
[24] Li H J(李慧嘉), Zhang J H(张俊华), Liu Z P(刘治平), Chen L N(陈洛南), Zhang X S(章祥荪). Identifying overlapping cmmnunities in socialnetworks using multi-scale 10cal information expansion, The European Physical Journal B, 85(6): 190, 2012.
[25] Li H J(李慧嘉), Liu Z P(刘治平), Chen L(陈洛南), Zhang X S(章祥荪). Identification of overlapping communities in protein interaction networks using multiscale local information expansion, IEEE World Congress on Intelligent Control and Automation, 5071-5076, 2012.
[26] Li W E T, Vanden-Eijnden E. Optimal partition and effective dynamics of complex networks, Proc. Natl. Acad. Sci. USA, 105(23): 7907-7912, 2008.
[27] Li Z(李珍萍), Zhang S(张世华), Wang R S(王瑞省), Zhang X S(章祥荪), Chen L(陈洛南). Quantitative function for community detection, Phys, Rev. E., 77, 036109, 2008.
[28] Lusseau D K, Schneider O J, Boisseau P, Haase Slooten E, Dawson E M. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behavioral ecology and sociobiology, 54, 396-405, 2003.
[29] Muchal P J, Richardson T, Maconl K, Porter M A, Onnela J P. Community structure in time-dependent, multiscale, and multiplex networks, Science, 328(5980): 876-878,2010.
[30] Murota K. Discrete convex Analysis, SIAM Philadelphia, 2003.
[31] Newman M E J, Girvan M. Finding and evaluating community structure in networks, Phys. Rev. E., 69(2): 026113, 2004.
[32] Newmau M E J, Modularity and Community structure in networks. Proc. Natl. Acad. Sci. USA, 103(23): 8577-8582, 2006.
[33] Newmau M E J. Community detection and graph partitioning, submitted to Europhys. Lett., 2013.
[34] Papadimitriou C H, Steiglitz K. Combinatorial optimization: algorithms and complexity, Prentice-Hall, inc, 1962.
[35] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks, Proc. Natl. Acad. Sci. USA, 101(9): 2658, 2004.
[36] Ravasz E, Somera A L, Mongru D A, Oltvai Z N. Barabasi A L,Hierarchical organization of modularity in metabolic Networks, Science, 297(5586): 1551-1555, 2002.
[37] Rosvall M, Carl T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA, 105(4): 1118-1123, 2008.
[38] Stoer M, Wagner F, A simple min-cut algorithm, J. ACM, 44(4): 585-591, 1997.
[39] Wang J(王吉光), Qiu Y(邱宇青), Wang R-S(王瑞省), Zhang X S(章祥荪). Remarks on network community properties, J. SYst, Sci. and. Complexity, 21: 637-644, 2008.
[40] Wang J(王吉光), Wang L(王林), Qiu Y Q(邱宇青), Wang Y(王勇). Zhang X S(章祥荪). A constrained optimization method for community detection, Lecture Notes in Operations Research, the Third International Symposium, OSB'09, Zhangjiajie, China, September, 20-22, 2009.
[41] Wang R S(王瑞省), Zhang S(张世华), Wang Y(王勇), Zhang X S(章祥荪), Chen L(陈洛南). Clustering complex networks and biological networks by Nonnegative Matrix Factorization with various silnilarity measures, Neurocomputing, 72, 134-141, 2008.
[42] Wang Y(王勇), Wang J(王吉光), Chen C(陈晨), Zhang X S(章祥荪). A regularized optimization model for community identification in complex networks, the tenth International Symposium on Operations Research and Its Applications(ISORA 2011), 147-156, 2011.
[43] Watts D J, Strogatz S H, Collective dynamics of'small-world'networks,Nature, 393, 440-442, 1998.
[44] Weinan E. Tiejun li Eric Vanden-Eijnden, Optimal partition and elfective dynamics of complex networks, Proc Natl. Acad. Sci. USA, 105(23): 7907-7912, 2007.
[45] Whitey S, Smythy P. A spectral clustering approach to finding communities in gtraphs,5-th SIAM International Conference on Data Mining, 2005.
[46] Zachary W W. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452-473, 1977.
[47] Zhang J(张俊华), Zhang S(张世华), Zhang X S(章祥荪). Detecting community structure in complex networks based on a measure of information discrepancy reference,Physica A, 387(7), 1675-1682, 2008.
[48] Zhang J(张俊华), Qiu Y(邱宇青), Zhang X S(章祥荪). Detecting community structure:from parsimony to weighted parsimony. J. Syst. Sci. Complex 23: 1024-1036, 2010.
[49] Zhang S(张世华), Wang R S(王瑞省), Zhang X S(章祥荪). Identification of overlapping community structure in complex networks using fuzzy c-means clustering,Physica A, 374, 483-490, 2007.
[50] Zhang S(张世华), Wang R S(王瑞省), Zhang X S(章祥荪). Uncovering fuzzy cmmnunity structure in complex networks. Physical Review E, 76, 046103, 2007.
[51] Zhang S(张世华), Ning X(宁雪梅), Zhang X S(章祥荪). Graph kernels,hierarchical clustering,and network community structure: experiments and comparative analysis, European Physical J, B, 57: 67-74, 2007.
[52] Zhang S(张世华), Zhao J(赵俊飞), Zhang X S(章祥荪). Common community structure in time-varying networks. Physical Review. E, Statistical, nonlinear, and soft matter physics, 85(5-2): 056110, 2012.
[53] Zhang X S(章祥荪), Wang R S(王瑞省). Optimization analysis of modularity measures for network community detection, Optimization and System Biology, Lecture Notes in Operations Research, 9, 13-20, World Publishing Corporation, 2008.
[54] Zhang X S(章祥荪), Wang R S(王瑞省), Wang Y(王勇), Wang J(王吉光), Qiu Y(邱宇青), Wang L(王林), and Chen L(陈洛南). Modularity optimization in community detection of complex networks, EPL, 87: 38002, 2009.
[55] Zhang X S(章祥荪), Li Z P(李珍萍), Wang R S(王瑞省), Wang Y(王勇). A combinatorial model and algorithm for globally searching community Structure in Complex Networks, J. Comb. Optim., 23(4): 425-442, 2012.
[56] Zhang Z Y(张忠元), Wang Y(王勇), Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization. Physical Review E, 87(6): 062803, 2013.
[57] Zhang Z Y(张忠元). Community structure detection in complex networks with partial background information. EPL(Europhysics Letters), 101(4): 48005,2013.
[58] Zhang Z Y(张忠元). Community structure detection in social networks based on dictionary learning. Science China Information Sciences, 56(7): 1-12, 2013.
[59] 张忠元.基于字典学习的网络社团结构探测算法.中国科学:信息科学,41(11):1343-1355,2011.