Please wait a minute...
Advanced Search
数据分析与知识发现  2022, Vol. 6 Issue (8): 1-11     https://doi.org/10.11925/infotech.2096-3467.2021.1358
  综述评介 本期目录 | 过刊浏览 | 高级检索 |
基于社会网络的结构多样性研究综述*
鲁英杰1,2,张应龙2()
1闽南师范大学计算机学院 漳州 363099
2闽南师范大学物理与信息工程学院 漳州 363099
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
全文: PDF (1235 KB)   HTML ( 39
输出: BibTeX | EndNote (RIS)      
摘要 

【目的】 对基于社会网络的结构多样性相关研究成果进行总结梳理并展望,为后续的相关研究提供参考与借鉴。【文献范围】 以“Structural Diversity”“Structural Diversity and Social Networks”“结构多样性”“结构多样性 and 社会网络”等检索式分别在Web of Science、Microsoft Academic、DBLP等英文数据库以及CNKI、万方、维普等中文数据库进行检索,限定发表时间为2012年4月至2022年4月,共得到1 619篇文献,经过整理阅读并通过引文网络或数据库检索等方式对代表性文献涉及的相关理论进行溯源,最终筛选出55篇相关文献进行评述。【方法】 对结构多样性进行理论溯源,分析概括其存在的问题,从模型改进、高效算法、实际应用三个主要方面论述结构多样性的研究现状,并对未来研究提出展望。【结果】 结构多样性为基于网络拓扑结构特征,研究影响个体做出重大决策机制的模型。但原始模型存在普适性较差、模型精度不够高等问题,与图挖掘技术结合优化后表现优秀,已被应用于多领域中。【局限】 只针对结构多样性研究进行梳理总结,未能与其他社会传染理论进行比较。【结论】 图挖掘算法可以在一定程度上消除结构多样性模型存在的群体划分缺陷;结构多样性可以作为寻找高影响力节点的指标且需要高效搜索算法作为支撑;结构多样性已在行为预测、链接预测等领域有所应用,并可与其他特征组合优化模型,但依旧需要更多实际应用的检验。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
鲁英杰
张应龙
关键词 结构多样性社会计算社会网络分析    
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 wordsStructural Diversity    Social Computing    Social Networks Analysis
收稿日期: 2021-11-30      出版日期: 2022-09-23
ZTFLH:  TP305  
基金资助:*国家自然科学基金项目的研究成果之一(61762036)
通讯作者: 张应龙,ORCID:0000-0002-3293-3257     E-mail: zhang_yinglong@126.com
引用本文:   
鲁英杰, 张应龙. 基于社会网络的结构多样性研究综述*[J]. 数据分析与知识发现, 2022, 6(8): 1-11.
Lu Yingjie, Zhang Yinglong. Review of Structural Diversity Studies on Social Networks. Data Analysis and Knowledge Discovery, 2022, 6(8): 1-11.
链接本文:  
https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2021.1358      或      https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/Y2022/V6/I8/1
Fig.1  结构多样性示意图
Fig.2  结构多样性与无向图图挖掘技术结合示意图
方法 图例 说明 diva
2-size分解法[4] 图2(a) 节点gh均是规模为1的连通分量,将节点gh删除 2
2-core分解法[4] 图2(b) 节点gh是度数为1的节点,删除节点gh及相关边后,发现节点ef的度数也为1,继续迭代,图中无度数小于2的节点,停止迭代 1
1-brace分解法[4] 图2(c) 节点bf没有公共节点,则边ebf的嵌入度为0,将边ebf删除 2
4-truss分解法[22] 图2(d) ebfedf的支持度均为1 < 4-2=2,则将边ebfedf 删除 2
Table 1  结构多样性与无向图图挖掘技术结合结果
Fig.3  结构多样性与有向图图挖掘技术结合示意图
方法 图例 说明 diva
弱连通性法[21] 图3(a) H1H2各为图中的一个连通分量 2
强连通性法[21] 图3(b) 节点ge彼此不能相互到达,则节点g独立于H2,节点h同理 4
4-clip分解法[21] 图3(c) 节点j的出度为4,删除相关节点和边后,继续迭代,图中无出度大于或等于4的节点,停止迭代 2
Table 2  结构多样性与有向图图挖掘技术结合结果
算法 优化策略 时间复杂度 空间复杂度
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 )
Table 3  基于k-size分解法的结构多样性Top-k搜索算法
Fig.4  结构多样性发展脉络
[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] 高伊林,闵超. 中美对“一带一路”沿线技术扩散结构比较研究*[J]. 数据分析与知识发现, 2021, 5(6): 80-92.
[2] 李跃艳,王昊,邓三鸿,王伟. 近十年信息检索领域的研究热点与演化趋势研究——基于SIGIR会议论文的分析[J]. 数据分析与知识发现, 2021, 5(4): 13-24.
[3] 关鹏,王曰芬. 国内外专利网络研究进展*[J]. 数据分析与知识发现, 2020, 4(1): 26-39.
[4] 陈芬, 付希, 何源, 薛春香. 融合社会网络分析与影响力扩散模型的微博意见领袖发现研究*[J]. 数据分析与知识发现, 2018, 2(12): 60-67.
[5] 王忠义, 张鹤铭, 黄京, 李春雅. 基于社会网络分析的网络问答社区知识传播研究[J]. 数据分析与知识发现, 2018, 2(11): 80-94.
[6] 李飞, 张健, 王宗水. 社会化推荐研究进展与发展趋势演化*——基于文献计量和社会网络分析的视角[J]. 数据分析与知识发现, 2017, 1(6): 22-35.
[7] 范如霞, 曾建勋, 高亚瑞玺. 基于合作网络的学者动态学术影响力模式识别研究[J]. 数据分析与知识发现, 2017, 1(4): 30-37.
[8] 岳子静, 章成志, 周清清. 基于UGC的中国各地区用户饮食偏好挖掘研究*[J]. 数据分析与知识发现, 2017, 1(11): 84-93.
[9] 王曰芬,靳嘉林. 比较分析《现代图书情报技术》近10年发文特征与发展趋势*[J]. 现代图书情报技术, 2016, 32(9): 1-16.
[10] 吴应良, 姚怀栋, 李成安. 一种引入间接信任关系的改进协同过滤推荐算法[J]. 现代图书情报技术, 2015, 31(9): 38-45.
[11] 任妮, 周建农. 合著网络加权模式下科研团队的发现与评价研究[J]. 现代图书情报技术, 2015, 31(9): 68-75.
[12] 谭旻, 许鑫. 学术博客推荐网络的h度实证——以科学网博客为例[J]. 现代图书情报技术, 2015, 31(7-8): 31-36.
[13] 黄微, 高俊峰, 王晨, 齐玥. 基于社会网络分析的隐性知识推送服务方法研究[J]. 现代图书情报技术, 2014, 30(2): 48-54.
[14] 周姗姗, 毕强, 高俊峰. 基于社会网络分析的信息检索结果可视化呈现方法研究[J]. 现代图书情报技术, 2013, 29(11): 81-85.
[15] 梁辰, 徐健. 社会网络可视化的技术方法与工具研究[J]. 现代图书情报技术, 2012, 28(5): 7-15.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn