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