Computer Science ›› 2018, Vol. 45 ›› Issue (6): 32-35.doi: 10.11896/j.issn.1002-137X.2018.06.005

• WISA2017 • Previous Articles     Next Articles

K-clique Heuristic Algorithm for Influence Maximization in Social Network

HU Qing-cheng, ZHANG Yong, XING Chun-xiao   

  1. Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;
    Research Institute of Information Technology,Tsinghua University,Beijing 100084,China
  • Received:2017-03-11 Online:2018-06-15 Published:2018-07-24

Abstract: Influence maximization is the problem of obtaining a set of nodes with specified size in social network to ma-ximize their aggregate influence under certain influence diffusion model,and it can yield significant benefit both in theory and real life.Influence maximization has been proved to be NP-hard by Kempe D et al.This paper proposed a new algorithm for influence maximization named K-clique Heuristic.The basic idea of the algorithm is that the nodes in social network spans multiple social circles.If these nodes are more widely spread in field and range,they have greater intersectionality and influence.The experimental results show that the proposed model is effective,and it may also shed light on the profound problem of influence maximization in social network.

Key words: Social network, Influence maximization, Information diffusion, Greedy algorithm, K-clique

CLC Number: 

  • TP311
[1]REN X L,LV L Y.Review of ranking nodes in complex networks[J].Chinese Science Bulletin,2014,59(13),1175-1197.(in Chinese)
任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,59(13):1175-1197.
[2]LIU J G,REN Z M,GUO Q,et al.Node importance ranking of complex network[J].Chinese Journal of Physics,2013,62(17):178901.(in Chinese)
刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J].物理学报,2013,62(17):178901.
[3]DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2001:57-66.
[4]RICHARDSON M,DOMINGOS P.Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2002:61-70.
[5]KEMPE D,KLEINBERG J,TARDOS E.Maximizing thespread of influence through as ocial network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137-146.
[6]CHEN W,WANG Y,YANG S.E cient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2009:199-208.
[7]KIMURA M,SAITO K.Tractable models for information diffusion in social networks[M]//Knowledge Discovery in Databases(PKDD 2006).Springer,2006:259-271.
[8]CHEN W,YUAN Y,ZHANG L.Scalable influence maximization in social networks under the linear threshold model[C]//2010 IEEE 10th International Conference on Data Mining (ICDM).IEEE,2010:88-97.
[9]WANG Y,CONG G,SONG G,et al.Community-based greedy algorithm for mining top-k influential nodes in mobile social networks[C]//Proceedings of the 16th ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining.ACM,2010:1039-1048.
[10]GALSTYAN A,MUSOYAN V,COHEN P.Maximizing influence propagation in networks with community structure[J].Physical Review E,2009,79(5):056102.
[11]LI D,XU Z M,CHAKRABORTY N,et al.Polarity related influence maximization in signed social networks[J].PloS one,2014,9(7):e102199.
[12]HU Q,ZHANG Y,XU X,et al.RMDN:New Approach to Maximize Influence Spread[C]//2015 IEEE 39th Annual Computer Software and Applications Conference.IEEE,2015:702-711.
[13]MARSDEN P V.Egocentric and sociocentric measures of network centrality[J].Social Networks,2002,24(4):407-422.
[14]WALKER G,KOGUT B,SHAN W.Social capital,structural holes and the formation of an industry network[J].Organization Science,1997,8(2):109-125.
[15]AHUJA G.Collaboration networks,structural holes,and innovation:A longitudinal study[J].Administrative Science Quarterly,2000,45(3):425-455.
[16]BURT R S.Structural holes:The social structure of competition[M].Cambridge:Harvard University Press,2009.
[17]PALLA G,DERE'NYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[18]XIE N.Social network analysis of blogs[D].United Kingdom: University of Bristol,2006.
[19]BOCCALETTI S,LATORA V,MORENO Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4):175-308.
[1] SUN Yong-yue, LI Hong-yan, ZHANG Jin-bo. RAISE:Efficient Influence Cost Minimizing Algorithm in Social Network [J]. Computer Science, 2019, 46(9): 59-65.
[2] LIU Xiao-jie, LV Xiao-qiang, WANG Xiao-ling, ZHANG Wei, ZHAO An. Mining User Interests on Twitter Using Wikipedia Category Graph [J]. Computer Science, 2019, 46(9): 79-84.
[3] ZHANG Zheng, WANG Hong-zhi, DING Xiao-ou, LI Jian-zhong, GAO Hong. Identification of Same User in Social Networks [J]. Computer Science, 2019, 46(9): 93-98.
[4] LIAO Yong, YANG Xin-yi, XIA Mao-han, WANG Bo, LI Shou-zhi, SHEN Xuan-fan. Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios [J]. Computer Science, 2019, 46(8): 121-126.
[5] LIU Chang-yun,YANG Yu-di,ZHOU Li-hua,ZHAO Li-hong. Discovering Popular Social Location with Time Label [J]. Computer Science, 2019, 46(7): 186-194.
[6] SHI Jun-ling,WANG Xing-wei,HUANG Min. Content-centric Routing Scheme in Vehicular Social Networks [J]. Computer Science, 2019, 46(7): 50-55.
[7] LI Zhuo, XU Zhe, CHEN Xin, LI Shu-qin. Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing [J]. Computer Science, 2019, 46(6): 102-106.
[8] LV Zhi-quan, LI Hao, ZHANG Zong-fu, ZHANG Min. Topic-based Re-identification for Anonymous Users in Social Network [J]. Computer Science, 2019, 46(6): 143-147.
[9] ZHENG Fei-feng, JIANG Juan, MEI Qi-huang. Study on Stowage Optimization in Minimum Container Transportation Cost [J]. Computer Science, 2019, 46(6): 239-245.
[10] YUAN De-yu, GAO Jian, YE Meng-xi, WANG Xiao-juan,. Malicious Information Source Locating Algorithm Based on Topological Extension in Online Social Network [J]. Computer Science, 2019, 46(5): 129-134.
[11] HUANG Jian-yi, LI Jian-jiang, WANG Zheng, FANG Ming-zhe. Single-Pass Short Text Clustering Based on Context Similarity Matrix [J]. Computer Science, 2019, 46(4): 50-56.
[12] HAN Zhong-ming, ZHENG Chen-ye, DUAN Da-gao, DONG Jian. Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning [J]. Computer Science, 2019, 46(4): 77-82.
[13] WU Jie-hua,SHEN Jing,ZHOU Bei. Community Features Based Balanced Modularity Maximization Social Link Prediction Model [J]. Computer Science, 2019, 46(3): 253-259.
[14] ZHAO Qian-qian, LV Min, XU Yin-long. Estimating Graphlets via Two Common Substructures Aware Sampling in Social Networks [J]. Computer Science, 2019, 46(3): 314-320.
[15] XU Fang, DENG Min, XIONG Zeng-gang, YE Cong-huan, XU Ning. Data Forwarding Algorithm Based on Multidimensional Context Matching in Mobile Social Networks [J]. Computer Science, 2019, 46(2): 81-87.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .