Positive effect of key player detection in social networks

doi:10.7523/j.issn.2095-6134.2019.03.017

Abstract

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

CLC Number:

TP399

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

References

[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.