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

所属专题： Artificial Intelligence and Pattern Recognition； Data Management and Data Mining

• Artificial Intelligence and Pattern Recognition • 上一篇    下一篇

一种有效使用社交行为计算社交网络中影响力节点的两相模型

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
  • 收稿日期:2016-12-13 修回日期:2017-10-14 出版日期:2018-03-05 发布日期:2018-03-05
  • 作者简介: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

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

PDF (PC)

1385

社交网络中的影响力度量在数据挖掘社区引起了广泛关注。影响最大化是指寻找有影响力的用户的过程，这些用户能最大化地利用信息或产品。在现实环境中，一个用户在某个社交网络的影响可以通过此社交网络的其他用户在其发表的事物上表现的一系列行为（如，点赞，分享，转发，评论）来建立模型。据我们所知，现有模型中对这些行为同等对待。然而，很显然，对某发表"点赞"的影响力比不上对它"分享"。这说明每个行为的影响（或重要性）有它的等级。本文针对社交网络中影响力最大化提出了一个模型：基于社会行为的影响力最大化模型，SAIM。在SAIM中，对某个个体的影响力进行度量时，不同行为不会同等对待，并且此过程分为两个主要步骤。首先，我们计算社交网络中每个个体的影响力，这个主要通过使用PageRank分析用户行为实现。最终我们得到一个加权社会网络，在此，每个节点由其影响力标记。接着，我们使用一个新概念"influence-BFS tree"计算一组优化的影响力节点。对大规模现实和合成社交网络上的实验表明，在可接受的时间范围内，我们的模型SAIM在计算最小一组影响力节点时性能良好，此组节点可最大化传播信息。

Abstract: 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] 张钹; 张铃;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] 孟力明; 徐晓飞; 常会友; 陈光熙; 胡铭曾; 李生;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] 林琦; 夏培肃;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] 冯玉琳;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[5] 孙成政; 慈云桂;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[6] 张钹; 张恬; 张建伟; 张铃;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[7] 郑崇勋; 张克农;. Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis[J]. , 1990, 5(2): 203 -209 .
[8] 王鼎兴; 郑纬民; 杜晓黎; 郭毅可;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[9] 周权; 魏道政;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[10] 赵靓海; 刘慎权;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：