[1]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报编辑部,2015,10(4):508-517.[doi:10.3969/j.issn.1673-4785.201408006]
LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10(4):508-517.[doi:10.3969/j.issn.1673-4785.201408006]
点击复制
LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10(4):508-517.[doi:10.3969/j.issn.1673-4785.201408006]
复杂网络结构比对算法研究进展
《智能系统学报》编辑部[ISSN 1673-4785/CN 23-1538/TP] 卷:
10
期数:
2015年第4期
页码:
508-517
栏目:
综述
出版日期:
2015-08-25
- Title:
- Advances in algorithms for construction alignment of complex networks research
- Keywords:
- complex networks; quadratic programming; topology identification; graph theory; alignment; network analysis; node cluster; dynamic analysis
- 分类号:
- TP391;O212
- 文献标志码:
- A
- 摘要:
- 复杂网络的结构比对问题在生物科学、计算机科学和社会科学等多个领域都具有很重要的现实意义。近年来涌现出了很多针对不同类型复杂网络的结构对比算法,对现有的网络结构比对算法进行梳理,重点分析了基于图的网络结构比对方法和基于数学框架网络结构比对方法。对这2种方法的特点进行了总结与比较,重点阐述了网络结构比对研究中的关键问题,分析和总结了现有的网络结构比对算法,阐述了网络结构比对中优势和不足。以此为基础提出了复杂网络结构比对问题未来的研究方向。
- Abstract:
- The construction alignment of complex networks problems in biological science、computer science、social science and other fields have practical signification. In recent years, different types of construction alignment of complex networks have been sprung up. In this paper, we mainly analysed the construction alignment algorithms based on graph and construction alignment algorithms and mathematical framework.Illustrating the key problem in the study of the networks alignment algorithm is analyzed and compared the algorithms of construction alignment. We explained their advantages and disadvantages,at last we forecast the future progress of algorithms for construction alignment of complex networks.
- 参考文献/References:
-
[1] STELZL U, WORM U, LALOWSKI M, et al. A human protein-protein interaction network: a resource for annotating the proteome[J]. Cell, 2005, 122 (6): 957-968.
[2] REN B, ROBERT F, WYRICK J J, et al. Genome-wide location and function of DNA binding proteins[J]. Science, 2000, 290 (5500): 2306-2309.
[3] MICHOEL T, NACHTERGAELE B. Alignment and integration of complex networks by hypergraph-based spectral clustering[J]. Physical Review E, 2012, 86 (5): 056111.
[4] ERDO S P, R NYI A. On the evolution of random graphs[J]. American Mathematical Society, 1960, 517-561.
[5] BONNICI V, GIUGNO R, PULVIRENTI A, et al. A subgraph isomorphism algorithm and its application to biochemical data[J]. BMC bioinformatics, 2013, 14 (Suppl 7): S13.
[6] KHAN A M, GLEICH D F, POTHEN A, et al. A multithreaded algorithm for network alignment via approximate matching[C]//2012 International Conference on proceedings of the High Performance Computing, Networking, Storage and Analysis (SC). 2012.
[7] TODOR A, DOBRA A, KAHVECI T. Probabilistic biological network alignment[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 2013, 10 (1): 109-121.
[8] SHVAIKO P, EUZENAT J. Ontology matching: state of the art and future challenges[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25 (1): 158-176.
[9] BOCK J, HETTENHAUSEN J. Discrete particle swarm optimisation for ontology alignment[J]. Information Sciences, 2012, 192: 152-173.
[10] HU W, JIAN N, QU Y, et al. Gmo: a graph matching for ontologies[C]//proceedings of the Proceedings of K-CAP Workshop on Integrating Ontologies. 2005: 42-48.
[11] MELNIK S, GARCIA-MOLINA H, RAHM E. Similarity flooding: a versatile graph matching algorithm and its application to schema matching[C]//Proceedings of the Proc 18th ICDE Conf(Best Student Paper award). 2002.
[12] KLAU G W. A new graph-based method for pairwise global network alignment[J]. BMC bioinformatics, 2009, 10(Suppl 1): S59.
[13] SINGH R, XU J, BERGER B. Pairwise global alignment of protein interaction networks by matching neighborhood topology[J]. 2007: 16-31.
[14] SINGH R, XU J, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences, 2008, 105 (35): 12763-12768.
[15] LAWLER E L. The quadratic assignment problem[J]. Management Science, 1963, 9 (4): 586-599.
[16] MISENER R, FLOUDAS C A. GloMIQO: Global mixed-integer quadratic optimizer[J]. Journal of Global Optimization, 2012, 57 (1):
[17] RIECK J, ZIMMERMANN J, GATHER T. Mixed-integer linear programming for resource leveling problems[J]. European Journal of Operational Research, 2012, 221 (1): 27-37.
[18] BRADDE S, BRAUNSTEIN A, MAHMOUDI H, et al. Aligning graphs and finding substructures by a cavity approach[J]. EPL (Europhysics Letters), 2010, 89 (3): 37009.
[19] BAYATI M, GERRITSEN M, GLEICH D F, et al. Algorithms for large, sparse network alignment problems[J]. 2009, 705-710.
[20] EL-KEBIR M, HERINGA J, KLAU G W. Lagrangian relaxation applied to sparse global network alignment[M]. Springer. 2011: 225-236.
[21] GUIGNARD M, KIM S. Lagrangean decomposition: a model yielding stronger Lagrangean bounds[J]. Mathematical Programming, 1987, 39 (2): 215-228.
[22] SINGH R, XU J, BERGER B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105 (35): 12763-12768.
[23] KECECIOGLU J. The maximum weight trace problem in multiple sequence alignment[C]//proceedings of the Combinatorial pattern matching. Springer.1993: 106-119.
[24] SAMATOVA N F. Global alignment of pairwise protein interaction networks for maximal common conserved patterns[J]. International Journal of Genomics, 2013: 670623.
[25] BAUER M, KLAU G W, REINERT K, et al. Accurate multiple sequence-structure alignment of RNA sequences[J]. BMC Bioinformatics, 2009: 15-33.
[26] BAYATI M, SHAH D, SHARMA M. Max-product for maximum weight matching: convergence, correctness, and LP duality[J]. IEEE Transactions on Information Theory, 2008, 54 (3): 1241-1251.
[27] BAYATI M, GERRITSEN M, GLEICH D F, et al. Algorithms for large, sparse network alignment problems[C]//09 Ninth IEEE International Conference on proceedings of the Data Mining, 2009: 705-710.
[28] PEARL J. Reverend Bayes on inference engines: a distributed hierarchical approach[C]//proceedings of the AAAI. 1982: 133-136.
[29] SANGHAVI S, MALIOUTOV D M, WILLSKY A S. Linear programming analysis of loopy belief propagation for weighted matching[C]//proceedings of the NIPS, 2007:.
[30] DAGUM L, MENON R. OpenMP: an industry standard API for shared-memory programming[J]. IEEE Transactions on Computational Science & Engineering, 1998, 5 (1): 46-55.
[31] JUNG J, MORI T, SUGITA Y. Midpoint cell method for hybrid (MPI+OpenMP) parallelization of molecular dynamics simulations[J]. Journal of computational chemistry, 2014: 1064-1072.
[32] THOMAN P, JORDAN H, PELLEGRINI S, et al. Automatic OpenMP loop scheduling: a combined compiler and runtime approach[M]. Springer, 2012: 88-101.
[33] GOUVEIA A, SILVA N, ROCHA J, et al. Iterative ontology alignment debugging using a scenario-and strategy-driven approach[C]// International Workshop on proceedings of the Database and Expert Systems Applications (DEXA), 2012\: 254-258.
[34] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[J]. 1999: 102-109.
[35] LIAO C-S, LU K, BAYM M, et al. IsoRankN: spectral methods for global alignment of multiple protein networks[J]. Bioinformatics, 2009, 25 (12): i253-i258.
[36] ANDERSEN R, CHUNG F, LANG K. Local graph partitioning using pagerank vectors[C]//47th Annual IEEE Symposium on proceedings of the Foundations of Computer Science, 2006 2006:.
[37] ALADAG A E, ERTEN C. SPINAL: scalable protein interaction network alignment[J]. Bioinformatics, 2013, 29 (7): 917-924.
[38] KELLEY B P, YUAN B, LEWITTER F, et al. PathBLAST: a tool for alignment of protein interaction networks[J]. Nucleic acids research, 2004, 32 (suppl 2): W83-W88.
[39] SHARAN R, SUTHRAM S, KELLEY R M, et al. Conserved patterns of protein interaction in multiple species[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102 (6): 1974-1979.
[40] KOYUT RK M, KIM Y, TOPKARA U, et al. Pairwise alignment of protein interaction networks[J]. Journal of Computational Biology, 2006, 13 (2): 182-199.
[41] FLANNICK J, NOVAK A, SRINIVASAN B S, et al. Graemlin: general and robust alignment of multiple large interaction networks[J]. Genome Research, 2006, 16 (9): 1169-1181.
[42] FLANNICK J, NOVAK A, DO C B, et al. Automatic parameter learning for multiple network alignment[C]//Proceedings of the Research in Computational Molecular Biology, F, 2008: 214-231.
[43] WANG B, GAO L. Seed selection strategy in global network alignment without destroying the entire structures of functional modules[J]. Proteome science, 2012, 10 (Suppl 1): S16.
[44] KOV CS I A, PALOTAI R, SZALAY M S, et al. Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics[J]. PloS one, 2010, 5 (9): e12528.
[45] MILENKOVIC T, ADVISER-PRZULJ N. From topological network analyses and alignments to biological function, disease, and evolution[M]. California State University at Long Beach, 2010
[46] ATIAS N, SHARAN R. Comparative analysis of protein networks: hard problems, practical solutions[J]. Communications of the ACM, 2012, 55 (5): 88-97.
[47] MILENKOVI C T, PRZULJ N. Uncovering biological network function via graphlet degree signatures[J]. Cancer informatics, 2008, (6): 56-65.
[48] MILLS-TETTEY G A, STENTZ A, DIAS M B. The dynamic hungarian algorithm for the assignment problem with changing costs[J]. 2007: 1-19.
[49] WEST D B. Introduction to graph theory[M]. Prentice hall Upper Saddle River, 2001: 178-185.
[50] MEMI?EVIC V, PRZULJ N. C-GRAAL: Common-neighbors-based global GRAph ALignment of biological networks[J]. Integrative Biology, 2012, 4 (7): 734-743.
[51] DUAN R, PETTIE S. Linear-Time Approximation for Maximum Weight Matching[J]. Journal of the ACM (JACM), 2014, 61 (1): 1.
[52] KOLLIAS G, MOHAMMADI S, GRAMA A. Network Similarity Decomposition (NSD): A fast and scalable approach to network alignment[J]. Knowledge and Data Engineering, IEEE Transactions on, 2012, 24 (12): 2232-2243.
[53] HUANG Q, WU L-Y, ZHANG X-S. Corbi: A new R package for biological network alignment and querying[J]. BMC Systems Biology, 2013, 7 (2): 1-9.
[54] PIJPERS V, DE LEENHEER P, GORDIJN J, et al. Using conceptual models to explore business-ICT alignment in networked value constellations[J]. Requirements Engineering, 2012, 17 (3): 203-226.
[55] KEARNS M, SINGH S. Near-optimal reinforcement learning in polynomial time[J]. Machine Learning, 2002, 49 (2-3): 209-232.
[56] LIU G, LI J, WONG L. Assessing and predicting protein interactions using both local and global network topological metrics[J]. Genome Informatics, 2008, 22 138-149.
[57] KUCHAIEV O, RA?AJSKI M, HIGHAM D J, et al. Geometric de-noising of protein-protein interaction networks[J]. PLoS computational biology, 2009, 5 (8): e1000454.
[58] CHUA H N, SUNG W-K, WONG L. Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions[J]. Bioinformatics, 2006, 22 (13): 1623-1630.
[59] NABIEVA E, JIM K, AGARWAL A, et al. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps[J]. Bioinformatics, 2005, 21 (suppl 1): i302-i310.
[60] ALI W, DEANE C M. Functionally guided alignment of protein interaction networks for module detection[J]. Bioinformatics, 2009, 25 (23): 3166-3173.
[61] CLAUSET A, MOORE C, NEWMAN M E. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453 (7191): 98-101.
[62] PR?ULJ N. Biological network comparison using graphlet degree distribution[J]. Bioinformatics, 2007, 23 (2): e177-e183.
[63] ZHU L, YOU Z-H, HUANG D-S. Increasing the reliability of protein-protein interaction networks via non-convex semantic embedding[J]. Neurocomputing, 2013, v121,p99-107.
[64] TERRADOT L, DURNELL N, LI M, et al. Biochemical Characterization of Protein Complexes from the Helicobacter pylori Protein Interaction Map Strategies for Complex Formation and Evidence for Novel Interactions Within Type IV Secretion Systems[J]. Molecular & Cellular Proteomics, 2004, 3 (8): 809-819.
[65] SUN P G, GAO L, SHAN HAN S. Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks[J]. Information Sciences, 2011, 181 (6): 1060-1071.
[66] HAVEMANN F, GL SER J, HEINZ M, et al. Identifying overlapping and hierarchical thematic structures in networks of scholarly papers: A comparison of three approaches[J]. PloS one, 2012, 7 (3): e33255.
[67] LEE C, REID F, MCDAID A, et al. Seeding for pervasively overlapping communities[J]. Physical Review E, 2011, 83 (6).
[68] DENT J E, YANG X, NARDINI C. SPNConverter: a new link between static and dynamic complex network analysis[J]. Bioinformatics, 2013, 29 (19): 2507-2508.
[69] WANG J, PENG X, PENG W, et al. Dynamic protein interaction network construction and applications[J]. Proteomics, 2014, 14 (4-5): 338-352.
[70] VAN DEN HOF P M, DANKERS A, HEUBERGER P S, et al. Identification of dynamic models in complex networks with prediction error methods—Basic methods for consistent module estimates[J]. Automatica, 2013, 49 (10): 2994-3006.
[71] MA’AYAN A. Insights into the organization of biochemical regulatory networks using graph theory analyses[J]. Journal of biological chemistry, 2009, 284 (9): 5451-5455.
- 相似文献/References:
-
[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报编辑部,2008,3(2):95.
WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,3():95.
[2]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报编辑部,2009,4(5):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
XIA Cheng-yi,LIU Zhong-xin,CHEN Zeng-qiang,et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems,2009,4():392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[3]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报编辑部,2011,6(1):57.
LI Wei,YANG Xiaofeng,ZHANG Chongyang,et al.A clustering method for community detection on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():57.
[4]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报编辑部,2011,6(3):208.
SUN Shiwen,XIA Chengyi,WANG Li.Survey of the measurement of software structures based on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():208.
[5]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报编辑部,2013,8(2):128.[doi:10.3969/j.issn.1673-4785.201210027]
ZHAO Jing,XIA Chengyi,SUN Shiwen,et al.A novel SIR model with infection delay and nonuniform transmission in complex networks[J].CAAI Transactions on Intelligent Systems,2013,8():128.[doi:10.3969/j.issn.1673-4785.201210027]
[6]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报编辑部,2014,9(6):734.[doi:10.3969/j.issn.1673-4785.201311014]
QIU Jianping,CHEN Lichao,PAN Lihu.Synchronization in complex networks via pinning control[J].CAAI Transactions on Intelligent Systems,2014,9():734.[doi:10.3969/j.issn.1673-4785.201311014]
[7]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报编辑部,2015,10(4):577.[doi:10.3969/j.issn.1673-4785.201411031]
CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,10():577.[doi:10.3969/j.issn.1673-4785.201411031]
[8]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报编辑部,2015,10(6):949.[doi:10.11992/tis.201507042]
WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,10():949.[doi:10.11992/tis.201507042]
[9]花小朋,孙一颗,丁世飞.一种改进的投影孪生支持向量机[J].智能系统学报编辑部,2016,11(3):384.[doi:10.11992/tis.201603049]
HUA Xiaopeng,SUN Yike,DING Shifei.An improved projection twin support vector machine[J].CAAI Transactions on Intelligent Systems,2016,11():384.[doi:10.11992/tis.201603049]
[10]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报编辑部,2016,11(3):426.[doi:10.11992/tis.201603045]
ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,11():426.[doi:10.11992/tis.201603045]
备注/Memo
收稿日期:2014-12-25;改回日期:。
基金项目:吉林省重点科技攻关项目(20140204046);生物芯片自动识别系统(20100505).
作者简介:刘富,男,1968年生,博士生导师,博士,博士,主要研究方向为模式识别与智能系统。参与国家博士后科学基金项目,国家863计划项目,国家自然科学基金项目,国家信息产业部项目,吉林省科技发展重大项目以及某部委预研基金项目等。发表论文20多篇;姜奕含,女,1990年生,硕士研究生,主要研究方向为模式识别中的网络的比对分析研究。
通讯作者:刘富.E-mail:liufu@jlu.edu.cn.
更新日期/Last Update:
2015-08-28