社交网络关键节点检测的积极效应问题

doi:10.7523/j.issn.2095-6134.2019.03.017

中国科学院大学学报 ›› 2019, Vol. 36 ›› Issue (3): 425-432.DOI: 10.7523/j.issn.2095-6134.2019.03.017

• 简报 • 上一篇

社交网络关键节点检测的积极效应问题

王新栋¹, 于华¹, 江成²

1. 中国科学院大学工程科学学院, 北京 100049;
2. 首都经济贸易大学信息学院, 北京 100070

收稿日期:2017-12-29 修回日期:2018-04-18 发布日期:2019-05-15
通讯作者: 江成
基金资助:
国家自然科学基金（71450009）和首都经济贸易大学2018年度科研基金资助

Positive effect of key player detection in social networks

WANG Xindong¹, YU Hua¹, JIANG Cheng²

1. School of Engineering Science, University of Chinese Academy of Sciences, Beijing 100049, China;
2. School of Information, Capital University of Economics and Business, Beijing 100070, China

Received:2017-12-29 Revised:2018-04-18 Published:2019-05-15

摘要/Abstract

摘要： 在社交网络中，识别有影响力的关键节点对于调控网络至关重要，是网络科学最前沿热点的研究内容。然而，现有方法大多基于局部特征进行求解，缺乏对网络整体结构的建模。为有效地解决这个问题，针对社交网络关键节点检测积极效应问题KPP-POS（key player problem positive），在KPP-POS的检测指标D_R的基础上，建立关键节点积极效应模型的0-1整数线性规划模型（0-1 integer linear programming key players problem positive effects model，IP-KPP-POS），进而提出一种计算复杂度较低且精确度较高的局部搜索启发式算法。最后通过多种人造网络和真实网络的实验分析，验证IP-KPP-POS模型在解决社交网络关键节点检测积极效应问题上的正确性和有效性。

关键词: 社交网络, 0-1整数线性规划, 关键节点, 网络优化, 启发式算法

Abstract: Identifying influential nodes has been one of the most intensive studies among network analysis, and it is essential to control social networks. However, most of the existing methods are based on local features and lack the modeling of the overall network structure. In order to solve the key player problem positive (KPP-POS) problem effectively, we propose a 0-1 integer linear programming model (IP-KPP-POS) based on the detection standard D_R of KPP-POS. Then, we design a local search heuristic algorithm that significantly reduces the computational complexity and simultaneously achieves high accuracy. Finally, the effectiveness of our methods are validated by experiments with various synthetic networks and real-world networks.

Key words: social networks, 0-1 integer linear programming, critical nodes, network optimization, heuristic algorithm

中图分类号:

TP399

王新栋, 于华, 江成. 社交网络关键节点检测的积极效应问题[J]. 中国科学院大学学报, 2019, 36(3): 425-432.

WANG Xindong, YU Hua, JIANG Cheng. Positive effect of key player detection in social networks[J]. , 2019, 36(3): 425-432.

参考文献

[1] Borgatti P,Mehra A,Brass J,et al. Network analysis in the social sciences[J]. science,2009,323(5916):892-895.
[2] 王伟,刘军,蒋熙,等. 中国铁路网的拓扑特性[J]. 北京交通大学学报,2010,34(3):148-152.
[3] Zhou T,Fu Z Q,Wang B H. Epidemic dynamics on complex networks[J]. Progress in Natural Science,2005,16(5):452-457.
[4] Latora V,Marchiori M. How the science of complex networks can help developing strategies against terrorism[J]. Chaos,Solitons and Fractals,2004,20(1):69-75.
[5] Albert R,Jeong H,Barabasi A L. Error and attack tolerance of complex networks[J]. Nature,2000,406(6794):378-382.
[6] Kurant M,Thiran P,Hagmann. Error and attack tolerance of layered complex networks[J]. Physical Review E,2007,76(2):026103.
[7] 朱冠桦,蒋国平,夏玲玲. 社交网络上从众现象对谣言传播影响的研究[J]. 计算机科学,2016,43(2):135-139.
[8] 韩江漫. 基于动态复杂网络技术的病毒传播控制策略研究[J]. 计算机与数字工程,2017,45(10):2004-2008.
[9] 曹照. 基于相继故障的复杂脑网络研究[D]. 兰州:兰州理工大学,2016.
[10] 薛红艳. 金融危机通过资本市场对我国经济扩散研究[D]. 保定:河北大学,2014.
[11] 孙睿,罗万伯. 网络舆论中节点重要性评估方法综述[J]. 计算机应用研究,2012,29(10):3606-3608.
[12] Hu Q C,Gao Y,Ma P F,et al. A new approach to identify influential spreaders in complex networks[C]//Web-Age Information Management,Lecture Notes in Computer Science,New York:Springer,2013,62(14):99-104.
[13] 赵之滢,于海,朱志良,等. 基于网络社团结构的节点传播影响力分析[J]. 计算机学报,2014(4):753-766.
[14] Borgatti S P. Identifying sets of key players in a social network[J]. Computational & Mathematical Organization Theory,2006,12(1):21-34.
[15] Hussain D M A. Investigation of key-player problem in terrorist networks using Bayes conditional probability[M]. Handbook of Social Network Technologies and Applications,2010:523-547.
[16] Hamill J T,Deckro R F,Chrissis J W,et al. Analysis of layered social networks[J]. IO Sphere, 2008(1):27-33.
[17] McGuire R M,Deckro R F. The weighted key player problem for social network analysis[J]. Military Operations Research,2015,20(2):35-53.
[18] Yang J. Generalized key player problem[J]. Computational & Mathematical Organization Theory,2015,21(1):24-47.
[19] Lü L,Chen D,Ren X L,et al. Vital nodes identification in complex networks[J]. Physics Reports,2016,650:1-63.
[20] Arulselvan A,Commander C W,Elefteriadou L,et al. Detecting critical nodes in sparse graphs[J]. Computers and Operations Research,2009,36(7):2193-2200.
[21] Jiang C,Wang J Y,Yu H,et al. An optimal approach for critical node problem using semidefinite programming[J]. Physica A:Statistical Mechanics and its Application,2017,471:315-324.
[22] Krebs V E. Uncloaking terrorist networks[J/OL]. First Monday,2002,7(4)[2017-12-20]. http://firstmonday.org/ojs/index.php/fm/article/view/941/86.
[23] Mcauley J,Leskovec J. Learning to discover social circles in ego networks[C]//International Conference on Neural Information Processing Systems. Curran Associates Inc,2012:539-547.

社交网络关键节点检测的积极效应问题

Positive effect of key player detection in social networks

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	田玮, 朱廷劭. 基于深度学习的微博用户自杀风险预测[J]. 中国科学院大学学报, 2018, 35(1): 131-136.
[2]	倪平, 张玉清, 闻观行, 刘奇旭, 范丹. 基于群体特征的社交僵尸网络检测方法[J]. 中国科学院大学学报, 2014, 31(5): 691-700.
[3]	熊凯, 张玉清, 吕少卿. 一种针对在线社交网络的自动化僵尸账号攻击方案[J]. 中国科学院大学学报, 2014, 31(4): 548-554.