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: Greedy algorithm, Influence maximization, Information diffusion, K-clique, Social network

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] WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[2] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[3] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[4] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[5] YU Ai-xin, FENG Xiu-fang, SUN Jing-yu. Social Trust Recommendation Algorithm Combining Item Similarity [J]. Computer Science, 2022, 49(5): 144-151.
[6] CHANG Ya-wen, YANG Bo, GAO Yue-lin, HUANG Jing-yun. Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR [J]. Computer Science, 2022, 49(4): 56-66.
[7] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[8] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[9] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
[10] WANG Jian, WANG Yu-cui, HUANG Meng-jie. False Information in Social Networks:Definition,Detection and Control [J]. Computer Science, 2021, 48(8): 263-277.
[11] TAN Qi, ZHANG Feng-li, WANG Ting, WANG Rui-jin, ZHOU Shi-jie. Social Network User Influence Evaluation Algorithm Integrating Structure Centrality [J]. Computer Science, 2021, 48(7): 124-129.
[12] ZHANG Ren-zhi, ZHU Yan. Malicious User Detection Method for Social Network Based on Active Learning [J]. Computer Science, 2021, 48(6): 332-337.
[13] BAO Zhi-qiang, CHEN Wei-dong. Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation [J]. Computer Science, 2021, 48(4): 243-248.
[14] ZHANG Shao-jie, LU Xu-dong, GUO Wei, WANG Shi-peng, HE Wei. Prevention of Dishonest Behavior in Supply-Demand Matching [J]. Computer Science, 2021, 48(4): 303-308.
[15] ZHANG Hao-chen, CAI Ying, XIA Hong-ke. Delivery Probability Based Routing Algorithm for Vehicular Social Network [J]. Computer Science, 2021, 48(3): 289-294.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!