大规模网络关联研究综述

doi:10.16183/j.cnki.jsjtu.2018.10.025

摘要/Abstract

摘要： 随着大规模网络型数据在各个领域中涌现，网络型数据研究工作日益受到研究者们的重视.网络关联是近年来该领域中提出的新兴研究课题，其目的在于将单一零散的网络进行关联整合，例如将不同在线社交网络中的节点通过是否属于同一个用户来进行关联.网络关联可以通过数据整合，进一步提高数据的价值，为后续研究提供数据保障，具有十分重要的研究价值.研究者们针对不同的场景，提出了相应的网络关联算法.对该方向的研究成果进行总结梳理，并对其发展进行展望.

关键词: 网络关联, 蛋白质-蛋白质相互作用网络, 社交网络

Abstract: As the large-scale network data widely exists in various domains, complex network has drawn plenty of research attention. Among these researches, network alignment is a novel research topic proposed in recent years, which aims at revealing the underlying alignment among networks. For example, aligning online social networks by whether the accounts are held by the same user. Aligning the isolated networks leads to network data integration and provides pre-required data for subsequent researches and applications. Researchers have proposed several network aligners according to different scenarios. In this manuscript, we summarize the existing works and discuss the future directions for network alignment.

Key words: network alignment, protein-protein interaction networks, social network

中图分类号:

TP 33

曹雪智，张伟楠，俞勇. 大规模网络关联研究综述[J]. 上海交通大学学报（自然版）, 2018, 52(10): 1348-1356.

CAO Xuezhi,ZHANG Weinan,YU Yong. Aligning Large-Scale Networks: A Survey[J]. Journal of Shanghai Jiaotong University, 2018, 52(10): 1348-1356.

参考文献

［1］Lü L, ZHOU T. Link prediction in complex networks: A survey ［J］. Physica A: Statistical Mechanics and its Applications, 2011, 390(6): 1150-1170. ［2］CAO X, YU Y. Joint user modeling across aligned heterogeneous sites［C］//Proceedings of the 10th ACM Conference on Recommender Systems. Boston, MA, USA: ACM, 2016: 83-90. ［3］ZHANG J. Link prediction across heterogeneous social networks: A survey ［EB/OL］. (2014-03-20) ［2018-04-15］. http://www.ifmlab.org/files/paper/2014_survey_paper.pdf. ［4］DJEDDI W E, KHADIR M T. A dynamic multistra-tegy ontology alignment framework based on semantic relationship using WordNet ［EB/OL］. (2014-09-18) ［2018-04-15］. http://www.ceur-ws.org/Vol-825/paper_238.pdf. ［5］LIU J, ZHANG F, SONG X, et al. What’s in a name: An unsupervised approach to link users across communities ［C］//Proceedings of the sixth ACM International Conference on Web Search and Data Mining. Roma, Italy: ACM, 2013: 495-504. ［6］VOSECKY J, HONG D, SHEN V Y. User identification across multiple social networks ［C］//First International Conference on Networked Digital Technologies. Ostrava, Czech Republic: IEEE, 2009: 360-365. ［7］TAN S, GUAN Z, CAI D, et al. Mapping users across networks by manifold alignment on hypergraph ［C］//Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Québec, Canada: AAAI, 2014: 159-165. ［8］CAO X, YU Y. BASS: A bootstrapping approach for aligning heterogenous social networks ［C］//Joint European Conference on Machine Learning and Know-ledge Discovery in Databases. Riva del Garda, Italy: Springer, 2016: 459-475. ［9］BERG J, LSSIG M. Local graph alignment and motif search in biological networks ［J］. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(41): 14689-14694. ［10］CRAWFORD J, MILENKOVI T. GREAT: Graphlet edge-based network alignment ［C］//International Conference on Bioinformatics and Biomedicine (BIBM). Washington, DC, USA: IEEE, 2015: 220-227. ［11］MEMIEVI V, PRULJ N. C-GRAAL: Common-neighbors-based global graph alignment of biological networks ［J］. Integrative Biology, 2012, 4(7): 734-743 ［12］PATRO R, KINGSFORD C. Global network alignment using multiscale spectral signatures ［J］. Bioinformatics, 2012, 28(23): 3105-3114. ［13］SARAPH V, MILENKOVIC T. MAGNA: Maximizing accuracy in global network alignment ［J］. Bioinformatics, 2014, 30(20): 2931-2940. ［14］FRASER H B, HIRSH A E, Steinmetz L M, et al. Evolutionary rate in the protein interaction network ［J］. Science, 2002, 296: 750-752. ［15］FAISAL F E, MILENKOVI T. Dynamic networks reveal key players in aging ［J］. Bioinformatics, 2014, 30(12): 1721-1729. ［16］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. ［17］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. ［18］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. ［19］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. ［20］LIAO C S, LU K, BAYM M, et al. IsoRankN: Spectral methods for global alignment of multiple protein networks ［J］. Bioinformatics, 2009, 25(12): 253-258. ［21］FOSSUM E, FRIEDEL C C, RAJAGOPALA S V, et al. Evolutionarily conserved herpesviral protein interaction networks ［J］. PLoS Pathogens, 2009, 5(9): 1-13. ［22］ZASLAVSKIY M, BACH F, VERT J P. A path following algorithm for the graph matching problem ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2227-2242. ［23］KLAU G W. A new graph-based method for pairwise global network alignment ［J］. BMC Bioinformatics, 2009, 10(Sup1): S59. ［24］KUCHAIEV O, MILENKOVI T, MEMIEVI V, et al. Topological network alignment uncovers biological function and phylogeny ［J］. Journal of the Royal Society Interface, 2010, 7(50): 1341-1354. ［25］PRULJ N. Biological network comparison using graphlet degree distribution ［J］. Bioinformatics, 2007, 23(2): e177-e183. ［26］MILENKOVIC T, NG W L, HAYES W, et al. Optimal network alignment with graphlet degree vectors ［J］. Cancer Informatics, 2010, 9: 121-137. ［27］KUCHAIEV O, PRULJ N. Integrative network alignment reveals large regions of global network si-milarity in yeast and human ［J］. Bioinformatics, 2011, 27(10): 1390-1396. ［28］MALOD-DOGNIN N, PRULJ N. L-GRAAL: Lagrangian graphlet-based network aligner ［J］. Bioinformatics, 2015, 31(13): 2182-2189. ［29］KELLEY B P, YUAN B, LEWITTER F, et al. PathBLAST: A tool for alignment of protein interaction networks ［J］. Nucleic Acids Research, 2004, 32(Sup2): W83-W88. ［30］ZAFARANI R, LIU H. Connecting corresponding identities across communities ［C］//Proceedings of the Third International Conference on Weblogs and Social Media. San Jose, CA, USA: AAAI, 2009: 354-357. ［31］NUNES A, CALADO P, MARTINS B. Resolving user identities over social networks through supervised learning and rich similarity features ［C］//Proceedings of the 27th Annual ACM Symposium on Applied Computing. Trento, Italy: ACM, 2012: 728-729. ［32］MALHOTRA A, TOTTI L, MEIRA JR W, et al. Studying user footprints in different online social networks ［C］//International Conference on Advances in Social Networks Analysis and Mining. Istanbul, Turkey: IEEE, 2012: 1065-1070. ［33］LABITZKE S, TARANU I, HARTENSTEIN H. What your friends tell others about you: Low cost linkability of social network profiles ［C］//5th International ACM Workshop on Social Network Mining and Analysis. San Diego, CA, USA: ACM, 2011: 1065-1070. ［34］GOGA O, LEI H, PARTHASARATHI S H K, et al. Exploiting innocuous activity for correlating users across sites ［C］//Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro, Brazil: ACM, 2013: 447-458. ［35］LIU S, WANG S, ZHU F, et al. Hydra: Large-scale social identity linkage via heterogeneous beha-vior modeling ［C］//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, UT, USA: ACM, 2014: 51-62. ［36］MADIGAN D, GENKIN A, LEWIS D D, et al. Author identification on the large scale ［EB/OL］. ［2018-04-15］. https://www.researchgate.net/publication/265579735_Author_Identification_on_the_Large_Scale. ［37］CHASKI C E. Empirical evaluations of language-based author identification techniques ［J］. Forensic Linguistics, 2001, 8(1): 1-65. ［38］BACKSTROM L, DWORK C, KLEINBERG J. Wherefore art thou R3579X? Anonymized social networks, hidden patterns, and structural steganography ［C］//Proceedings of the 16th International Conference on World Wide Web. Banff, Alberta, Canada: ACM, 2007: 181-190. ［39］CAO X, YU Y. ASNets: A benchmark dataset of aligned social networks for cross-platform user modeling ［C］//Proceedings of the 25th ACM International Conference on Information and Knowledge Management. Indianapolis, IN, USA: ACM, 2016: 1881-1884.

[1]	吴春旭，黄一络，许传永. 正负网络效应共存的社交平台定价问题[J]. 上海交通大学学报（自然版）, 2015, 49(04): 519-523.
[2]	谢婧, 刘功申, 苏波, 孟魁. 社交网络中的用户转发行为预测[J]. 上海交通大学学报（自然版）, 2013, 47(04): 583-588.