学报(中文)

大规模网络关联研究综述

展开
  • 上海交通大学APEX数据与知识管理实验室, 上海 200240
曹雪智(1991-),男,江苏省南京市人,博士生,主要从事社交网络以及用户建模研究.

Aligning Large-Scale Networks: A Survey

Expand
  • APEX Data & Knowledge Management Lab, Shanghai Jiao Tong University, Shanghai 200240, China

摘要

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

本文引用格式

曹雪智,张伟楠,俞勇 . 大规模网络关联研究综述[J]. 上海交通大学学报, 2018 , 52(10) : 1348 -1356 . DOI: 10.16183/j.cnki.jsjtu.2018.10.025

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.

参考文献

[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.
Options
文章导航

/