Please wait a minute...
Data Analysis and Knowledge Discovery  2022, Vol. 6 Issue (8): 1-11    DOI: 10.11925/infotech.2096-3467.2021.1358
Current Issue | Archive | Adv Search |
Review of Structural Diversity Studies on Social Networks
Lu Yingjie1,2,Zhang Yinglong2()
1School of Computer Science and Engineering, Minnan Normal University, Zhangzhou 363099, China
2School of Physics and Information Engineering, Minnan Normal University, Zhangzhou 363099, China
Download: PDF (1235 KB)   HTML ( 40 ) 
Export: BibTeX | EndNote (RIS)      
Abstract  

[Objective] This paper reviews the latest developments of the structural diversity studies on social networks and discusses their future directions. [Coverage] We searched the Web of Science, Microsoft Academic, DBLP, CNKI, Wanfang Data and VIP with “Structural Diversity”, “Structural Diversity and Social Networks ”. A total of 55 representative and related literature published from April 2012 to April 2022 were retrieved. [Methods] First, we traced to the source of structural diversity studies and analyzed their existing issues. Then, we examined the structural diversity research from three perspectives: model improvements, efficient algorithms, and practical applications. Finally, we discussed future works. [Results] Structural diversity is a model based on network topology features, which studies factors affecting individuals’ major decision makings. The original model has the bad universality and low precision issues. Combined with graph mining technology, the new model performs well and has been applied in many fields. [Limitations] We only summarized research on structural diversity and did not compare them with other social contagion theories. [Conclusions] Graph mining algorithm could improve the structural diversity model in group division. Structural diversity is an indicator for finding highly influential nodes and required by efficient search algorithms. Structural diversity has been applied in the fields of behavior and link predictions. Features optimizing this model merit more research to evaluated their performance.
Key words： Structural Diversity      Social Computing      Social Networks Analysis     
Received: 30 November 2021      Published: 23 September 2022
ZTFLH:  TP305  
Fund:National Natural Science Foundation of China(61762036)
Corresponding Authors: Zhang Yinglong,ORCID：0000-0002-3293-3257     E-mail: zhang_yinglong@126.com
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Yingjie Lu
Yinglong Zhang

Cite this article:

Lu Yingjie, Zhang Yinglong. Review of Structural Diversity Studies on Social Networks. Data Analysis and Knowledge Discovery, 2022, 6(8): 1-11.

URL:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.2096-3467.2021.1358     OR     https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2022/V6/I8/1

Illustration of the Structural Diversity
Illustration of Structural Diversity Combined with Undirected Graph Mining
方法 图例 说明 div（a）
2-size分解法[4] 图2（a） 节点g、h均是规模为1的连通分量,将节点g、h删除 2
2-core分解法[4] 图2（b） 节点g、h是度数为1的节点,删除节点g、h及相关边后,发现节点e、f的度数也为1,继续迭代,图中无度数小于2的节点,停止迭代 1
1-brace分解法[4] 图2（c） 节点b、f没有公共节点,则边ebf的嵌入度为0,将边ebf删除 2
4-truss分解法[22] 图2（d） 边ebf、edf的支持度均为1 < 4-2=2,则将边ebf、edf 删除 2
Conclusion of Structural Diversity Combined with Undirected Graph Mining
Illustration of Structural Diversity Combined with Directed Graph Mining
方法 图例 说明 div（a）
弱连通性法[21] 图3（a） H1与H2各为图中的一个连通分量 2
强连通性法[21] 图3（b） 节点g、e彼此不能相互到达,则节点g独立于H2,节点h同理 4
4-clip分解法[21] 图3（c） 节点j的出度为4,删除相关节点和边后,继续迭代,图中无出度大于或等于4的节点,停止迭代 2
Conclusion of Structural Diversity Combined with Directed Graph Mining
算法 优化策略 时间复杂度 空间复杂度
Degree-
Based[25]		 度上限剪枝 O ∑ v ∈ V d v 2 O ( m )
Bound-
Search[25]		 不相交集合森林
动态度上限剪枝		 O ∑ v ∈ V d v 2 O ( m )
Fast-Bound-
Search[25]		 遍历规则
哈希		 O ( α m ) O ( m )
A?-Bound-
Search[25]		 遍历规则 O ( ( α + l o g d v ) m ) O ( m )
Div-TriE[26] 度全序 O ( α m h ) O ( m )
Div-TriE*[26] 哈希优化 O ( α m ) O ( m n )
Algorithms on k-size Decomposition Based Top-k Structural Diversity Search
Development of Structural Diversity
[1] 罗俊. 计算·模拟·实验: 计算社会科学的三大研究方法[J]. 学术论坛, 2020, 43(1): 35-49.
[1] (Luo Jun. Computing, Simulation and Experiment: Three Research Methods of Computational Social Science[J]. Academic Forum, 2020, 43(1): 35-49.)
[2] Lazer D, Pentland A, Adamic L, et al. Social Science. Computational Social Science[J]. Science, 2009, 323(5915): 721-723.
doi: 10.1126/science.1167742
[3] 孟小峰, 李勇, 祝建华. 社会计算:大数据时代的机遇与挑战[J]. 计算机研究与发展, 2013, 50(12): 2483-2491.
[3] (Meng Xiaofeng, Li Yong, Zhu Jianhua. Social Computing in the Era of Big Data: Opportunities and Challenges[J]. Journal of Computer Research and Development, 2013, 50(12): 2483-2491.)
[4] Ugander J, Backstrom L, Marlow C, et al. Structural Diversity in Social Contagion[J]. PNAS, 2012, 109(16): 5962-5966.
doi: 10.1073/pnas.1116502109 pmid: 22474360
[5] Aggarwal C. Social Network Data Analytics[M]. New York: Springer, 2011.
[6] Bon G L. The Crowd: A Study of the Popular Mind[M]. New York: Dover Publications, 2002.
[7] Latané B. The Psychology of Social Impact[J]. American Psychologist, 1981, 36(4): 343-356.
doi: 10.1037/0003-066X.36.4.343
[8] Jones M B, Jones D R. Preferred Pathways of Behavioral Contagion[J]. Journal of Psychiatric Research, 1995, 29(3): 193-209.
pmid: 7473296
[9] Hodas N O, Lerman K. The Simple Rules of Social Contagion[J]. Scientific Reports, 2014, 4: Article No.4343.
[10] Coleman J, Katz E, Menzel H. The Diffusion of an Innovation among Physicians[A]// Social Networks[M]. Amsterdam: Elsevier, 1977: 107-124.
[11] Bakshy E, Eckles D, Yan R, et al. Social Influence in Social Advertising: Evidence from Field Experiments[C]// Proceedings of the 13th ACM Conference on Electronic Commerce. 2012: 146-161.
[12] Watts D J. A Simple Model of Global Cascades on Random Networks[J]. PNAS, 2002, 99(9): 5766-5771.
doi: 10.1073/pnas.082090499
[13] Hasan S, Ukkusuri S V. A Threshold Model of Social Contagion Process for Evacuation Decision Making[J]. Transportation Research Part B: Methodological, 2011, 45(10): 1590-1605.
doi: 10.1016/j.trb.2011.07.008
[14] 何高奇, 边晓晖, 孙菲, 等. 基于传染病机制的突发事件下群体情绪感染模型[J]. 华东理工大学学报(自然科学版), 2018, 44(6): 909-917, 949.
[14] (He Gaoqi, Bian Xiaohui, Sun Fei, et al. Crowd Emotional Contagion Model Based on the Epidemic Mechanism under Emergencies[J]. Journal of East China University of Science and Technology (Natural Science Edition), 2018, 44(6):909- 917, 949.)
[15] 王祯骏, 王树徽, 张维刚, 等. 基于社交内容的潜在影响力传播模型[J]. 计算机学报, 2016, 39(8): 1528-1540.
[15] (Wang Zhenjun, Wang Shuhui, Zhang Weigang, et al. Social Content Based Latent Influence Propagation Model[J]. Chinese Journal of Computers, 2016, 39(8): 1528-1540.)
[16] Su J, Kamath K, Sharma A, et al. An Experimental Study of Structural Diversity in Social Networks[C]// Proceedings of the 14th International AAAI Conference on Web and Social Media. 2020: 661-670.
[17] Liang H. Decreasing Social Contagion Effects in Diffusion Cascades: Modeling Message Spreading on Social Media[J]. Telematics and Informatics, 2021, 62: Article No.101623.
[18] Granovetter M S. The Strength of Weak Ties[J]. American Journal of Sociology, 1973, 78(6): 1360-1380.
doi: 10.1086/225469
[19] Friedkin N E. Information Flow Through Strong and Weak Ties in Intraorganizational Social Networks[J]. Social Networks, 1982, 3(4): 273-285.
doi: 10.1016/0378-8733(82)90003-X
[20] Lazega E, Burt R S. Structural Holes: The Social Structure of Competition[J]. Revue Française de Sociologie, 1995, 36(4): Article No.779.
[21] Zhang Y F, Wang L, Zhu J J H, et al. The Strength of Structural Diversity in Online Social Networks[J]. Research, 2021, 2021(4): 117-126.
[22] Huang J B, Huang X, Xu J L. Truss-Based Structural Diversity Search in Large Graphs[C]// Proceedings of 2021 IEEE 37th International Conference on Data Engineering. 2021: 2346-2347.
[23] Huang J B, Huang X, Zhu Y Y, et al. Parameter-Free Structural Diversity Search[C]// Proceedings of Web Information Systems Engineering. 2019: 677-693.
[24] Huang J B, Huang X, Zhu Y Y, et al. Parallel Algorithms for Parameter-Free Structural Diversity Search on Graphs[J]. World Wide Web, 2021, 24(1): 397-417.
doi: 10.1007/s11280-020-00843-6
[25] Huang X, Cheng H, Li R H, et al. Top-K Structural Diversity Search in Large Networks[J]. The VLDB Journal, 2015, 24(3): 319-343.
doi: 10.1007/s00778-015-0379-0
[26] Chang L J, Zhang C, Lin X M, et al. Scalable Top-K Structural Diversity Search[C]// Proceedings of the 33rd International Conference on Data Engineering.IEEE, 2017: 95-98.
[27] Zhang Q, Li R H, Yang Q X, et al. Efficient Top-K Edge Structural Diversity Search[C]// Proceedings of the 36th International Conference on Data Engineering. IEEE, 2020: 205-216.
[28] 陈芬, 付希, 何源, 等. 融合社会网络分析与影响力扩散模型的微博意见领袖发现研究[J]. 数据分析与知识发现, 2018, 2(12): 60-67.
[28] (Chen Fen, Fu Xi, He Yuan, et al. Identifying Weibo Opinion Leaders with Social Network Analysis and Influence Diffusion Model[J]. Data Analysis and Knowledge Discovery, 2018, 2(12): 60-67.)
[29] Xu W Z, Liang W F, Lin X L, et al. Finding Top-K Influential Users in Social Networks Under the Structural Diversity Model[J]. Information Sciences, 2016, 355-356: 110-126.
[30] Huang X Y, Tiwari M, Shah S. Structural Diversity in Social Recommender Systems[C]// Proceedings of the 5th ACM RecSys Workshop on Recommender Systems and the Social Web. 2013.
[31] Fang Z P, Zhou X Y, Tang J, et al. Modeling Paying Behavior in Game Social Networks[C]// Proceedings of the 23rd ACM International Conference. 2014: 411-420.
[32] Gao S, Ma J, Chen Z M. Popularity Prediction in Microblogging Network[C]// Proceedings of Asia-Pacific Web Conference. 2014: 379-390.
[33] Seidman S B. Network Structure and Minimum Degree[J]. Social Networks, 1983, 5(3): 269-287.
doi: 10.1016/0378-8733(83)90028-X
[34] 白林根, 谌志群, 王荣波, 等. 微博关注关系网络K-核结构实证分析[J]. 现代图书情报技术, 2013(11): 68-74.
[34] (Bai Lingen, Chen Zhiqun, Wang Rongbo, et al. Empirical Analysis on K-core of Microblog Following Relationship Network[J]. New Technology of Library and Information Service, 2013(11): 68-74.)
[35] Emerson A I, Andrews S, Ahmed I, et al. K-Core Decomposition of a Protein Domain Co-occurrence Network Reveals Lower Cancer Mutation Rates for Interior Cores[J]. Journal of Clinical Bioinformatics, 2015, 5: Arcicle No.1.
[36] He X, Zhao H, Cai W, et al. Analyzing the Structure of Earthquake Network by K-Core Decomposition[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 421(1): 34-43.
doi: 10.1016/j.physa.2014.11.022
[37] Cohen J D. Trusses: Cohesive Subgraphs for Social Network Analysis[J]. National Security Agency Technical Report, 2008: 1-29.
[38] Moody J, White D R. Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups[J]. American Sociological Review, 2003, 68(1): 103-127.
doi: 10.2307/3088904
[39] Guo R C, Shaabani E, Bhatnagar A, et al. Toward Early and Order-of-Magnitude Cascade Prediction in Social Networks[J]. Social Network Analysis and Mining, 2016, 6(1): 1-18.
doi: 10.1007/s13278-015-0311-z
[40] Marin E, Guo R, Shakarian P. Temporal Analysis of Influence to Predict Users’ Adoption in Online Social Networks[C]// Proceedings of International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction and Behavior Representation in Modeling and Simulation. 2017: 254-261.
[41] Yuan Y, Altenburger K M, Kooti F. Causal Network Motifs: Identifying Heterogeneous Spillover Effects in A/B Tests[C]// Proceedings of the Web Conference 2021. 2021: 3359-3370.
[42] Sánchez-Arrieta N, González R A, Cañabate A, et al. Social Capital on Social Networking Sites: A Social Network Perspective[J]. Sustainability, 2021, 13(9): 5147.
doi: 10.3390/su13095147
[43] Aral S, Nicolaides C. Exercise Contagion in a Global Social Network[J]. Nature Communications, 2017, 8(1): Article No. 14753.
[44] Spiliotopoulos T, Oakley I. Understanding Motivations for Facebook Use: Usage Metrics, Network Structure, and Privacy[C]// Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. 2013: 3287-3296.
[45] Zhang J, Liu B, Tang J, et al. Social Influence Locality for Modeling Retweeting Behaviors[C]// Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013: 2761-2767.
[46] Dong Y X, Johnson R A, Xu J, et al. Structural Diversity and Homophily: A Study Across More than One Hundred Big Networks[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 807-816.
[47] Sanz-Cruzado J, Castells P. Enhancing Structural Diversity in Social Networks by Recommending Weak Ties[C]// Proceedings of the 12th ACM Conference on Recommender Systems. 2018: 233-241.
[48] Bao Q, Cheung W K, Zhang Y, et al. A Component-Based Diffusion Model with Structural Diversity for Social Networks[J]. IEEE Transactions on Cybernetics, 2017, 47(4): 1078-1089.
doi: 10.1109/TCYB.2016.2537366
[49] Backstrom L, Kleinberg J, Lee L, et al. Characterizing and Curating Conversation Threads: Expansion, Focus, Volume, Re-Entry[C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 2013: 13-22.
[50] Qiu J Z, Tang J, Ma H, et al. DeepInf: Social Influence Prediction with Deep Learning[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 2110-2119.
[51] Gelper S, van der Lans R, van Bruggen G. Competition for Attention in Online Social Networks: Implications for Seeding Strategies[J]. Management Science, 2021, 67(2): 1026-1047.
doi: 10.1287/mnsc.2019.3564
[52] Malliaros F D, Giatsidis C, Papadopoulos A N, et al. The Core Decomposition of Networks: Theory, Algorithms and Applications[J]. The VLDB Journal, 2020, 29(1): 61-92.
doi: 10.1007/s00778-019-00587-4
[53] Chen C M. Searching for Intellectual Turning Points: Progressive Knowledge Domain Visualization[J]. PNAS, 2004, 101(S1): 5303-5310.
doi: 10.1073/pnas.0307513100
[54] 王林旭, 严承希. 情报学领域人工智能相关研究的文献计量分析及探析[J]. 图书情报知识, 2020(1): 53-62.
[54] (Wang Linxu, Yan Chengxi. Bibliometric Analysis of Research on Artificial Inteligence in Information Science[J]. Documentation, Information & Knowledge, 2020(1): 53-62.)
[1] Yue Zijing,Zhang Chengzhi,Zhou Qingqing. Studying Dietary Preferences of Chinese Residents[J]. 数据分析与知识发现, 2017, 1(11): 84-93.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626，82624938   E-mail:jishu@mail.las.ac.cn