›› 2018, Vol. 33 ›› Issue (2): 286-304.doi: 10.1007/s11390-018-1820-9

Special Issue: Artificial Intelligence and Pattern Recognition; Data Management and Data Mining

• Artificial Intelligence and Pattern Recognition • Previous Articles     Next Articles

An Efficient Two-Phase Model for Computing Influential Nodes in Social Networks Using Social Actions

Mehdi Azaouzi, Lotfi Ben Romdhane   

  1. Modeling of Automated Reasoning Systems Research Laboratory LR17 ES05 Higher Institute of Computer Science and Telecom, University of Sousse, Sousse 526-4002, Tunisia
  • Received:2016-12-13 Revised:2017-10-14 Online:2018-03-05 Published:2018-03-05
  • Contact: 10.1007/s11390-018-1820-9
  • About author:Mehdi Azaouzi is currently a Ph.D. student at the National School of Computer Sciences, University of Manouba, Tunisia. He received his Bachelor's degree and his Master's degree from the Faculty of Sciences, University of Monastir, Tunisia, both in computer science, in 2009 and 2012, respectively. His current research interests include social networks analyses, graph mining, and graph indexing. He is member of the MARS (Modeling of Automated Reasoning Systems) Research Laboratory

The measurement of influence in social networks has received a lot of attention in the data mining community. Influence maximization refers to the process of finding influential users who make the most of information or product adoption. In real settings, the influence of a user in a social network can be modeled by the set of actions (e.g., "like", "share", "retweet", "comment") performed by other users of the network on his/her publications. To the best of our knowledge, all proposed models in the literature treat these actions equally. However, it is obvious that a "like" of a publication means less influence than a "share" of the same publication. This suggests that each action has its own level of influence (or importance). In this paper, we propose a model (called Social Action-Based Influence Maximization Model, SAIM) for influence maximization in social networks. In SAIM, actions are not considered equally in measuring the "influence power" of an individual, and it is composed of two major steps. In the first step, we compute the influence power of each individual in the social network. This influence power is computed from user actions using PageRank. At the end of this step, we get a weighted social network in which each node is labeled by its influence power. In the second step of SAIM, we compute an optimal set of influential nodes using a new concept named "influence-BFS tree". Experiments conducted on large-scale real-world and synthetic social networks reveal the good performance of our model SAIM in computing, in acceptable time scales, a minimal set of influential nodes allowing the maximum spreading of information.

[1] Farhadi F, Sorkhi M, Hashemi S, Hamzeh A. An effective framework for fast expert mining in collaboration networks:A group-oriented and cost-based method. Journal of Computer Science and Technology, 2012, 27(3):577-590.

[2] Bouguessa M, Ben Romdhane L. Identifying authorities in online communities. ACM Trans. Intelligent Systems and Technology, 2015, 6(3):Article No. 30.

[3] Lv L Y, Zhang Y C, Yeung C H, Zhou T. Leaders in social networks, the Delicious case. PLoS One, 2011, 6(6):Article No. e21202.

[4] Zhang B L, Qian Z Z, Li W Z, Tang B, Lu S L, Fu X M. Budget allocation for maximizing viral advertising in social networks. Journal of Computer Science and Technology, 2016, 31(4):759-775.

[5] Chen W, Li F, Lin T, Rubinstein A. Combining traditional marketing and viral marketing with amphibious influence maximization. In Proc. the 16th ACM Conf. Economics and Computation, June 2015, pp.779-796.

[6] Sangachin M, Samadi M, Cavuoto L. Modeling the spread of an obesity intervention through a social network. Journal of Healthcare Engineering, 2014, 5(3):293-312.

[7] Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N. Cost-effective outbreak detection in networks. In Proc. the 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2007, pp.420-429.

[8] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network. In Proc. the 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2003, pp.137-146.

[9] Domingos P, Richardson M. Mining the network value of customers. In Proc. the 7th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2001, pp.57-66.

[10] Chen W, Yuan Y F, Zhang L. Scalable influence maximization in social networks under the linear threshold model. In Proc. the 10th IEEE Int. Conf. Data Mining, December 2010, pp.88-97.

[11] Jung K, Heo W, Chen W. IRIE:Scalable and robust influence maximization in social networks. In Proc. the 12th Int. Conf. Data Mining, December 2012, pp.918-923.

[12] Wang C, Chen W, Wang Y J. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 2012, 25(3):545-576.

[13] Kim J, Kim S K, Yu H. Scalable and parallelizable processing of influence maximization for large-scale social networks? In Proc. the 29th Int. Conf. Data Engineering, April 2013, pp.266-277.

[14] Wang Q Y, Jin Y H, Lin Z, Cheng S D, Yang T. Influence maximization in social networks under an independent cascade-based model. Physica A:Statistical Mechanics and its Applications, 2016, 444:20-34.

[15] Bozorgi A, Haghighi H, Zahedi M S, Rezvani M. INCIM:A community-based algorithm for influence maximization problem under the linear threshold model. Information Processing & Management, 2016, 52(6):1188-1199.

[16] Goyal A, Lu W, Lakshmanan L V S. SIMPATH:An efficient algorithm for influence maximization under the linear threshold model. In Proc. the 11th Int. Conf. Data Mining, December 2011, pp.211-220.

[17] Rahimkhani K, Aleahmad A, Rahgozar M, Moeini A. A fast algorithm for finding most influential people based on the linear threshold model. Expert Systems with Applications, 2015, 42(3):1353-1361.

[18] Wang Y, Cong G, Song G J, Xie K Q. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In Proc. the 16th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, July 2010, pp.1039-1048.

[19] Jiang Q Y, Song G J, Cong G, Wang Y, Si W J, Xie K Q. Simulated annealing based influence maximization in social networks. In Proc. the 25th AAAI Conf. Artificial Intelligence, August 2011, pp.127-132.

[20] Tang Y Z, Shi Y C, Xiao X K. Influence maximization in near-linear time:A martingale approach. In Proc. ACM SIGMOD Int. Conf. Management of Data, May 31-June 4, 2015, pp.1539-1554.

[21] Li H, Cui J T, Ma J F. Social influence study in online networks:A three-level review. Journal of Computer Science and Technology, 2015, 30(1):184-199.

[22] Riquelme F, González-Cantergiani P. Measuring user influence on Twitter:A survey. Information Processing & Management, 2016, 52(5):949-975.

[23] Tejaswi V, Bindu P V, Thilagam P S. Diffusion models and approaches for influence maximization in social networks. In Proc. Int. Conf. Advances in Computing Communications and Informatics, September 2016, pp.1345-1351.

[24] Weng J S, Lim E P, Jiang J, He Q. TwitterRank:Finding topic-sensitive influential twitterers. In Proc. the 3rd ACM Int. Conf. Web Search and Data Mining, February 2010, pp.261-270.

[25] Barbieri N, Bonchi F, Manco G. Topic-aware social influence propagation models. Knowledge and Information Systems, 2013, 37(3):555-584.

[26] Xiang B, Liu Q, Chen E H, Xiong H, Zheng Y, Yang Y. PageRank with priors:An influence propagation perspective. In Proc. the 23rd Int. Joint Conf. Artificial Intelligence, August 2013, pp.2740-2746.

[27] Wang Y F, Vasilakos A V, Jin Q, Ma J H. PPRank:Economically selecting initial users for influence maximization in social networks. IEEE Systems Journal, 2017, 11(4):2279-2290.

[28] Wang G J, Jiang W J, Wu J, Xiong Z L. Fine-grained feature-based social influence evaluation in online social networks. IEEE Trans. Parallel and Distributed Systems, 2014, 25(9):2286-2296.

[29] Chen Y C, Chang S H, Chou C L, Peng W C, Lee S Y. Exploring community structures for influence maximization in social networks. In Proc. the 6th SNA-KDD Workshop, August 2012.

[30] Kandhway K, Kuri J. Using node centrality and optimal control to maximize information diffusion in social networks. IEEE Trans. Systems Man and Cybernetics:Systems, 2017, 47(7):1099-1110.

[31] Li H, Bhowmick S S, Sun A X, Cui J T. Conformityaware influence maximization in online social networks. The VLDB Journal, 2015, 24(1):117-141.

[32] Li H, Bhowmick S S, Sun A X. CASINO:Towards conformity-aware social influence analysis in online social networks. In Proc. the 20th ACM Int. Conf. Information and Knowledge Management, October 2011, pp.1007-1012.

[33] Li Y H, Chen W, Wang Y J, Zhang Z L. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In Proc. the 6th ACM Int. Conf. Web Search and Data Mining, February 2013, pp.657-666.

[34] He J, Kaur H, Talluri M. Positive opinion influential node set selection for social networks:Considering both positive and negative relationships. In Proc. Wireless Communications Networking and Applications, December 2014, pp.935-948.

[35] Guler B, Varan B, Tutuncuoglu K, Nafea M, Zewail A A, Yener A, Octeau D. Using social sensors for influence propagation in networks with positive and negative relationships. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(2):360-373.

[36] Liu S Y, Wang S H, Zhu F D, Zhang J B, Krishnan R. HYDRA:Large-scale social identity linkage via heterogeneous behavior modeling. In Proc. ACM SIGMOD Int. Conf. Management of Data, June 2014, pp.51-62.

[37] Liu S Y, Wang S H, Zhu F D. Structured learning from heterogeneous behavior for social identity linkage. IEEE Trans. Knowledge and Data Engineering, 2015, 27(7):2005-2019.

[38] Subbian K, Sharma D, Wen Z, Srivastava J. Finding influencers in networks using social capital. In Proc. IEEE/ACM Int. Conf. Advances in Social Networks Analysis and Mining, August 2013, pp.592-599.

[39] Franks H, Griffiths N, Anand S S. Learning influence in complex social networks. In Proc. Int. Conf. Autonomous Agents and Multi-agent Systems, May 2013, pp.447-454.

[40] Deng X H, Pan Y, Wu Y, Gui J S. Credit distribution and influence maximization in online social networks using node features. In Proc. the 12th Int. Conf. Fuzzy Systems and Knowledge Discovery, August 2015, pp.2093-2100.

[41] Liu G F, Zhu F, Zheng K, Liu A, Li Z X, Zhao L, Zhou X F. TOSI:A trust-oriented social influence evaluation method in contextual social networks. Neurocomputing, 2016, 210:130-140.

[42] Zeng Y F, Chen X F, Cong G, Qin S C, Tang J, Xiang Y P. Maximizing influence under influence loss constraint in social networks. Expert Systems with Applications, 2016, 55:255-267.

[43] Subbian K, Aggarwal C, Srivastava J. Mining influencers using information flows in social streams. ACM Trans. Knowledge Discovery from Data, 2016, 10(3):Article No. 26.

[44] Liu S Y, Chen L, Ni L M, Fan J P. CIM:Categorical influence maximization. In Proc. the 5th Int. Conf. Ubiquitous Information Management and Communication, February 2011, Article No. 124.

[45] Qu Q, Liu S Y, Jensen C S, Zhu F D, Faloutsos C. Interestingness-driven diffusion process summarization in dynamic networks. In Proc. European Conf. Machine Learning and Knowledge Discovery in Databases, September 2014, pp.597-613.

[46] On B W, Lim E P, Jiang J, Teow L N. Engagingness and responsiveness behavior models on the Enron email network and its application to email reply order prediction. In The Influence of Technology on Social Network Analysis and Mining, Özyer T, Rokne J, Wagner G, Reuser A H P (eds.), Springer, 2013, pp.227-253.

[47] Achananuparp P, Lim E P, Jiang J, Hoang T A. Who is retweeting the tweeters? Modeling, originating, and promoting behaviors in the Twitter network. ACM Trans. Management Information Systems, 2012, 3(3):Article No. 13.

[48] Zhao K, Yen J, Greer G, Qiu B J, Mitra P, Portier K. Finding influential users of online health communities:A new metric based on sentiment influence. Journal of the American Medical Informatics Association, 2014, 21(e2):e212-e218.

[49] Yang C C, Tang X N. Estimating user influence in the MedHelp social network. IEEE Intelligent Systems, 2012, 27(5):44-50.

[50] Nikolaev A, Gore S, Govindaraju V. Engagement capacity and engaging team formation for reach maximization of online social media platforms. In Proc. the 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2016, pp.225-234.

[51] Bonchi F, Castillo C, Gionis A, Jaimes A. Social network analysis and mining for business applications. ACM Trans. Intelligent Systems and Technology, 2011, 2(3):Article No. 22.

[52] Fang Q, Sang J T, Xu C S, Rui Y. Topic-sensitive influencer mining in interest-based social media networks via hypergraph learning. IEEE Trans. Multimedia, 2014, 16(3):796-812.

[53] Li J X, Liu C F, Yu J X, Chen Y, Sellis T, Culpepper J S. Personalized influential topic search via social network summarization. IEEE Trans. Knowledge and Data Engineering, 2016, 28(7):1820-1834.

[54] Chen Y C, Zhu W Y, Peng W C, Lee W C, Lee S Y. CIM:Community-based influence maximization in social networks. ACM Trans. Intelligent Systems and Technology, 2014, 5(2):Article No. 25.

[55] Budak C, Agrawal D, Abbadi A E. Limiting the spread of misinformation in social networks. In Proc. the 20th Int. Conf. World Wide Web, April 2011, pp.665-674.

[56] Al-Garadi M A, Varathan K D, Ravana S D. Identification of influential spreaders in online social networks using interaction weighted K-core decomposition method. Physica A:Statistical Mechanics and its Applications, 2017, 468:278-288.

[57] Chen W L, Cheng S Y, He X, Jiang F. InfluenceRank:An efficient social influence measurement for millions of users in microblog. In Proc. the 2nd Int. Conf. Cloud and Green Computing, November 2012, pp.563-570.

[58] Brin S, Page L. The anatomy of a large-scale hypertextual web search engine. In Proc. the 7th Int. World-Wide Web Conf., April 1998, pp.107-117.

[59] Lee S, Park S, Kahng M, Lee S G. PathRank:Ranking nodes on a heterogeneous graph for flexible hybrid recommender systems. Expert Systems with Applications, 2013, 40(2):684-697.

[60] Boyd S, Vandenberghe L. Convex Optimization (7th edition). Cambridge University Press, 2009.

[61] Goyal A, Lu W, Lakshmanan L V S. CELF++:Optimizing the greedy algorithm for influence maximization in social networks. In Proc. the 20th Int. Conf. Companion on World Wide Web, March 2011, pp.47-48.

[62] Heidari M, Asadpour M, Faili H. SMG:Fast scalable greedy algorithm for influence maximization in social networks. Physica A:Statistical Mechanics and its Applications, 2015, 420:124-133.

[63] Hu Y F. Efficient, high-quality force-directed graph drawing. The Mathematica Journal, 2006, 10(1):37-71.

[64] Bastian M, Heymann S, Jacomy M. Gephi:An open source software for exploring and manipulating networks. In Proc. the 3rd Int. AAAI Conf. Weblogs and Social Media, July 2009, pp.361-362.

[65] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 2008, 78(4):Article No. 046110.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Feng Yulin;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[5] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[6] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[7] Zheng Chongxun; Zhang Kenong;. Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis[J]. , 1990, 5(2): 203 -209 .
[8] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[9] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[10] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved