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] MA Li-bo, QIN Xiao-lin. Topic-Location-Category Aware Point-of-interest Recommendation [J]. Computer Science, 2020, 47(9): 81-87.
[2] CHEN Jin-yin, ZHANG Dun-Jie, LIN Xiang, XU Xiao-dong and ZHU Zi-ling. False Message Propagation Suppression Based on Influence Maximization [J]. Computer Science, 2020, 47(6A): 17-23.
[3] YANG Zhuo-xuan, MA Yuan-pei and YAN Guan. Polynomial Time Community Detection Algorithm Based on Coupling Strength [J]. Computer Science, 2020, 47(6A): 102-107.
[4] LIANG Jun-bin, ZHANG Min, JIANG Chan. Research Progress of Social Sensor Cloud Security [J]. Computer Science, 2020, 47(6): 276-283.
[5] KONG Fang, LI Qi-zhi, LI Shuai. Survey on Online Influence Maximization [J]. Computer Science, 2020, 47(5): 7-13.
[6] FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization [J]. Computer Science, 2020, 47(5): 96-102.
[7] ZHANG Xin-ming, LI Shuang-qian, LIU Yan, MAO Wen-tao, LIU Shang-wang, LIU Guo-qi. Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection [J]. Computer Science, 2020, 47(5): 217-224.
[8] LIU Xiao-fei, ZHU Fei, FU Yu-chen, LIU Quan. Personalized Recommendation Algorithm Based on User Preference Feature Mining [J]. Computer Science, 2020, 47(4): 50-53.
[9] SUN Zhi-qiang, WAN Liang, DING Hong-wei. Android Malware Detection Method Based on Deep Autoencoder Network [J]. Computer Science, 2020, 47(4): 298-304.
[10] WU Lei,YUE Feng,WANG Han-ru,WANG Gang. Academic Paper Recommendation Method Combined with Researcher Tag [J]. Computer Science, 2020, 47(2): 51-57.
[11] ZHANG Min-jun, HUA Qing-yi. Personalized Recommendation of Social Network Users' Interest Points Based on ProbabilityMatrix Decomposition Algorithm [J]. Computer Science, 2020, 47(12): 144-148.
[12] LI Xiao, QU Yang, LI Hui, GUO Shi-kai. User Importance Evaluation for Q&A Platform Based on User Relations [J]. Computer Science, 2020, 47(11A): 430-436.
[13] GU Qiu-yang, JU Chun-hua, WU Gong-xing. Social Network Information Recommendation Model Combining Deep Autoencoder and Network Representation Learning [J]. Computer Science, 2020, 47(11): 101-112.
[14] ZHAO Xia, LI Xian, ZHANG Ze-hua, ZHANG Chen-wei. Community Detection Algorithm Combing Community Embedding and Node Embedding [J]. Computer Science, 2020, 47(10): 121-125.
[15] HU Jun-qin, ZHANG Jia-jun, HUANG Yin-hao, CHEN Xing, LIN Bing. Computation Offloading Scheduling Technology for DNN Applications in Edge Environment [J]. Computer Science, 2020, 47(10): 247-255.
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 .
[3] 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 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] 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 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .