research-article

A generation probability based percolation network alignment method

Authors:

Ge YuAuthors Info & Claims

World Wide Web, Volume 24, Issue 5

Pages 1511 - 1531

https://doi.org/10.1007/s11280-021-00893-4

Published: 01 September 2021 Publication History

Abstract

With the rapid growth of Internet industry, online social networks have become an indivisible part of our lives. To enjoy different kinds of services, people prefer to take part in multiple online social networks rather than only one. Therefore, identifying the same user across networks, formally named as social network alignment, has become a hot research topic. In this paper, we use social network structure to solve this problem. Firstly, inspired by the aligned network model (a mathematical model to formalize the real-world aligned networks), we present a novel assumption for network alignment. We suppose that the real-world aligned networks can be seen as generated from many different underlying social networks, depending on the matching between users, and the correctly aligned networks ought to own the maximum generation probability. Secondly, a Generation probability based Percolation Network Alignment method (GPNA) is presented. In GPNA, only the candidates, which can increase the generation probability, are regarded as the matched users. At last, a series of experiments are conducted to demonstrate the good performance of GPNA on both synthetic networks and real-world networks.

References

[1]

Barabási A-L and Albert R Emergence of scaling in random networks science 1999 286 5439 509-512

[2]

Bayati, M., Gerritsen, M., Gleich, D.F., Saberi, A., Wang, Y.: Algorithms for large, sparse network alignment problems. In: 2009 Ninth IEEE International Conference on Data Mining, pp 705–710, IEEE (2009)

[3]

Blondel VD, Guillaume J-L, Lambiotte R, and Lefebvre E Fast unfolding of communities in large networks Journal of statistical mechanics: theory and experiment 2008 2008 10 P10008

[4]

Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, and Wagner D On modularity clustering IEEE transactions on knowledge and data engineering 2007 20 2 172-188

[5]

Chen, H., Yin, H., Sun, X., Chen, T., Gabrys, B., Musial, K.: Multi-level graph convolutional networks for cross-platform anchor link prediction. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp 1503–1511 (2020)

[6]

Chen, Z., Yu, X., Song, B., Gao, J., Hu, X., Yang, W-S: Community-based network alignment for large attributed network. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp 587–596, ACM (2017)

[7]

Chiasserini C-F, Garetto M, and Leonardi E De-anonymizing clustered social networks by percolation graph matching ACM Transactions on Knowledge Discovery from Data (TKDD) 2018 12 2 21

[8]

Chu, X., Fan, X., Yao, D., Zhu, Z., Huang, J., Bi, J.: Cross-network embedding for multi-network alignment. In: The World Wide Web Conference, pp 273–284, ACM (2019)

[9]

Dai OE, Cullina D, Kiyavash N, and Grossglauser M Analysis of a canonical labeling algorithm for the alignment of correlated erdos-rényi graphs Proceedings of the ACM on Measurement and Analysis of Computing Systems 2019 3 2 36

[10]

Erdös P and Rényi A On random graphs i Publ. Math. Debrecen 1959 6 290-297

[11]

Feizi, S., Quon, G., Medard, M., Kellis, M., Jadbabaie, A.: Spectral alignment of networks (2015)

[12]

Feng S, Shen D, Nie T, Kou Y, He J, and Yu G Inferring anchor links based on social network structure IEEE Access 2018 6 17340-17353

[13]

Fu H, Zhang A, and Xie X Effective social graph deanonymization based on graph structure and descriptive information ACM Transactions on Intelligent Systems and Technology (TIST) 2015 6 4 49

[14]

Fu S, Wang G, Xia S, and Liu L Deep multi-granularity graph embedding for user identity linkage across social networks Knowl.-Based Syst. 2020 193 105301

[15]

Heimann, M., Shen, H., Safavi, T., Koutra, D.: Regal: Representation learning-based graph alignment. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp 117–126, ACM (2018)

[16]

Karrer B and Newman MarkEJ Stochastic blockmodels and community structure in networks Physical review E 2011 83 1 016107

[17]

Kazemi, E., Grossglauser, M.: Mpgm: Scalable and accurate multiple network alignment. IEEE/ACM transactions on computational biology and bioinformatics (2019)

[18]

Kazemi E, Hassani SH, and Grossglauser M Growing a graph matching from a handful of seeds Proceedings of the VLDB Endowment 2015 8 10 1010-1021

[19]

Kong, X., Zhang, J., Yu, P.S.: Inferring anchor links across multiple heterogeneous social networks. In: Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pp 179–188, ACM (2013)

[20]

Korula N and Lattanzi S An efficient reconciliation algorithm for social networks Proceedings of the VLDB Endowment 2014 7 5 377-388

[21]

Li, C., Wang, S., Yu, P.S., Zheng, L., Zhang, X., Li, Z., Liang, Y.: Distribution distance minimization for unsupervised user identity linkage. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp 447–456, ACM (2018)

[22]

Li, H., Chen, Q., Zhu, H., Ma, D., Wen, H., Shen, X.S.: Privacy leakage via de-anonymization and aggregation in heterogeneous social networks. IEEE Transactions on Dependable and Secure Computing (2017)

[23]

Li Y, Peng Y, Zhang Z, Yin H, and Xu Q Matching user accounts across social networks based on username and display name World Wide Web 2019 22 3 1075-1097

[24]

Liu, L., Cheung, W.K., Li, X., Liao, L.: Aligning users across social networks using network embedding. In: IJCAI, pp 1774–1780 (2016)

[25]

Lubars, J., Srikant, R.: Correcting the output of approximate graph matching algorithms. In: IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp 1745–1753, IEEE (2018)

[26]

Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In: Security and Privacy, 2009 30th IEEE Symposium on, pp 173–187, IEEE (2009)

[27]

Nikolentzos, G., Meladianos, P., Vazirgiannis, M.: Matching node embeddings for graph similarity. In: Thirty-First AAAI Conference on Artificial Intelligence (2017)

[28]

Nilizadeh, S., Kapadia, A., Ahn, Y-Y: Community-enhanced de-anonymization of online social networks. In: Proceedings of the 2014 acm sigsac conference on computer and communications security, pp 537–548, ACM (2014)

[29]

Rosvall, M., Bergstrom, C.T.: Maps of information flow reveal community structure in complex networks. arXiv preprint physics.soc-ph/0707.0609 (2007)

[30]

Singh R, Xu J, and Berger B Global alignment of multiple protein interaction networks with application to functional orthology detection Proc. Natl. Acad. Sci. 2008 105 35 12763-12768

[31]

Viswanath, B., Mislove, A., Cha, M., Gummadi, P.K.: On the evolution of user interaction in facebook. In: Acm Workshop on Online Social Networks (2009)

[32]

Vosecky, J., Hong, D., Shen, V.Y.: User identification across multiple social networks. In: 2009 first international conference on networked digital technologies, pp 360–365, IEEE (2009)

[33]

Wang, Y., Feng, C., Chen, L., Yin, H., Guo, C., Chu, Y.: User identity linkage across social networks via linked heterogeneous network embedding. World Wide Web, pp. 1–22 (2018)

[34]

Yan, J., Yang, S., Hancock, E.R.: Learning for graph matching and related combinatorial optimization problems. In: International Joint Conference on Artificial Intelligence, York (2020)

[35]

Yartseva, L., Grossglauser, M.: On the performance of percolation graph matching. In: Proceedings of the first ACM conference on Online social networks, pp 119–130, ACM (2013)

[36]

Yu X, Sun Y, Bertino E, and Li X Modeling user intrinsic characteristic on social media for identity linkage ACM Transactions on Social Computing 2018 1 3 11

[37]

Zafarani, R., Liu, H.: Connecting corresponding identities across communities. In: Third International AAAI Conference on Weblogs and Social Media (2009)

[38]

Zhang, J., Philip, S.Y.: Integrated anchor and social link predictions across social networks. In: IJCAI, pp 2125–2132 (2015)

[39]

Zhang, Y., Tang, J., Yang, Z., Pei, J., Yu, P.S.: Cosnet: Connecting heterogeneous social networks with local and global consistency. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1485–1494, ACM (2015)

[40]

Zhang Z, Gu Q, Yue T, and Su S Identifying the same person across two similar social networks in a unified way: Globally and locally Inform. Sci. 2017 394 53-67

[41]

Zheng R, Li J, Chen H, and Huang Z A framework for authorship identification of online messages: Writing-style features and classification techniques Journal of the American society for information science and technology 2006 57 3 378-393

[42]

Zhong, Z., Cao, Y., Guo, M., Nie, Z.: Colink: An unsupervised framework for user identity linkage. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)

[43]

Zhou, F., Wen, Z., Trajcevski, G., Zhang, K., Zhong, T., Liu, F.: Disentangled network alignment with matching explainability. In: IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pp 1360–1368, IEEE (2019)

[44]

Zhou F, Zhang K, Xie S, and Luo X Learning to correlate accounts across online social networks: An embedding-based approach INFORMS J. Comput. 2020 32 3 714-729

[45]

Zhou X, Liang X, Du X, and Zhao J Structure based user identification across social networks IEEE Trans. Knowl. Data Eng. 2017 30 6 1178-1191

[46]

Zhou X, Liang X, Zhang H, and Ma Y Cross-platform identification of anonymous identical users in multiple social media networks IEEE transactions on knowledge and data engineering 2015 28 2 411-424

[47]

Zhu Y, Qin L, Yu JX, Ke Y, and Lin X High efficiency and quality: large graphs matching The VLDB Journal—The International Journal on Very Large Data Bases 2013 22 3 345-368

Cited By

Kilincer ITuncer TErtam FSengur A(2023)An automated internet of behavior detection method based on feature selection and multiple pooling using network dataMultimedia Tools and Applications10.1007/s11042-023-14810-682:19(29547-29565)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1007/s11042-023-14810-6

Index Terms

A generation probability based percolation network alignment method

Index terms have been assigned to the content through auto-classification.

Recommendations

Attribute Network Alignment Based on Network Embedding
ICCDE '21: Proceedings of the 2021 7th International Conference on Computing and Data Engineering

Nodes with similar network structure and attribute features probably distribute across different networks. For instance, people tend to have accounts across various social networks. In recent years, network alignment to identify potential ...
Scalable Heterogeneous Social Network Alignment through Synergistic Graph Partition
HT '20: Proceedings of the 31st ACM Conference on Hypertext and Social Media

Social network alignment has been an important research problem for social network analysis in recent years. With the identified shared users across networks, it will provide researchers with the opportunity to achieve a more comprehensive understanding ...
CANA: Causal-enhanced Social Network Alignment
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge Management

Social network alignment is widely applied in web applications for identifying corresponding nodes across different networks, such as linking users across two social networks. Existing methods for social network alignment primarily rely on alignment ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image World Wide Web

World Wide Web Volume 24, Issue 5

Sep 2021

495 pages

ISSN:1386-145X

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2021

Accepted: 03 May 2021

Revision received: 28 February 2021

Received: 08 June 2020

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kilincer ITuncer TErtam FSengur A(2023)An automated internet of behavior detection method based on feature selection and multiple pooling using network dataMultimedia Tools and Applications10.1007/s11042-023-14810-682:19(29547-29565)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1007/s11042-023-14810-6

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents