Social Graph Restoration via Random Walk Sampling

被引:0
作者
Nakajima, Kazuki [1 ]
Shudo, Kazuyuki [1 ]
机构
[1] Tokyo Inst Technol, Tokyo, Japan
来源
2022 IEEE 38TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2022) | 2022年
关键词
Social network analysis; social networks; social graphs; random walk; sampling; social graph restoration; MODELS; FRAMEWORK; NETWORKS;
D O I
10.1109/ICDE53745.2022.00065
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Analyzing social graphs with limited data access is challenging for third-party researchers. To address this challenge, a number of algorithms that estimate structural properties via a random walk have been developed. However, most existing algorithms are limited to the estimation of local structural properties. Here we propose a method for restoring the original social graph from the small sample obtained by a random walk. The proposed method generates a graph that preserves the estimates of local structural properties and the structure of the subgraph sampled by a random walk. We compare the proposed method with subgraph sampling using a crawling method and the existing method for generating a graph that structurally resembles the original graph via a random walk. Our experimental results show that the proposed method more accurately reproduces the local and global structural properties on average and the visual representation of the original graph than the compared methods. We expect that our method will lead to exhaustive analyses of social graphs with limited data access.
引用
收藏
页码:806 / 819
页数:14
相关论文
共 66 条
[1]   Network Sampling: From Static to Streaming Graphs [J].
Ahmed, Nesreen K. ;
Neville, Jennifer ;
Kompella, Ramana .
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2014, 8 (02)
[2]  
[Anonymous], 2007, P 16 INT C WORLD WID, DOI DOI 10.1145/1242572.1242685
[3]  
[Anonymous], 2011, ACM Journal of Experimental Algorithms
[4]  
Backstrom L, 2012, PROCEEDINGS OF THE 3RD ANNUAL ACM WEB SCIENCE CONFERENCE, 2012, P33
[5]   Parallel algorithms for evaluating centrality indices in real-world networks [J].
Bader, David A. ;
Madduri, Kamesh .
2006 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, PROCEEDINGS, 2006, :539-547
[6]  
Bastian M., 2009, P INT AAAI C WEB SOC, V3, DOI DOI 10.1136/QSHC.2004.010033
[7]   How to Count Triangles, without Seeing the Whole Graph [J].
Bera, Suman K. ;
Seshadhri, C. .
KDD '20: PROCEEDINGS OF THE 26TH ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY & DATA MINING, 2020, :306-316
[8]   Complex networks: Structure and dynamics [J].
Boccaletti, S. ;
Latora, V. ;
Moreno, Y. ;
Chavez, M. ;
Hwang, D. -U. .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2006, 424 (4-5) :175-308
[9]  
Bojchevski A, 2018, PR MACH LEARN RES, V80
[10]  
Borgatti Stephen, 2018, ANAL SOCIAL NETWORKS, DOI DOI 10.1080/0022250X.2015.1053371