Centrality Measures, Upper Bound, and Influence Maximization in Large Scale Directed Social Networks

• Autorzy: Pal S.K. , Kundu S. , Murthy C.A.

Identyfikatory

DOI

10.3233/FI-2014-994

• Języki publikacji: EN

Abstrakty

EN

The paper addresses the problem of finding top k influential nodes in large scale directed social networks. We propose two new centrality measures, Diffusion Degree for independent cascade model of information diffusion and Maximum Influence Degree. Unlike other existing centrality measures, diffusion degree considers neighbors' contributions in addition to the degree of a node. The measure also works flawlessly with non uniform propagation probability distributions. On the other hand, Maximum Influence Degree provides the maximum theoretically possible influence (Upper Bound) for a node. Extensive experiments are performed with five different real life large scale directed social networks. With independent cascade model, we perform experiments for both uniform and non uniform propagation probabilities. We use Diffusion Degree Heuristic (DiDH) and Maximum Influence Degree Heuristic (MIDH), to find the top k influential individuals. k seeds obtained through these for both the setups show superior influence compared to the seeds obtained by high degree heuristics, degree discount heuristics, different variants of set covering greedy algorithms and Prefix excluding Maximum Influence Arborescence (PMIA) algorithm. The superiority of the proposed method is also found to be statistically significant as per T-test.

Słowa kluczowe

EN

centrality measure; social network; influence maximization; independent cascade model; statistical significance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 3
• Strony: 317--342
• Opis fizyczny: Bibliogr. 27 poz., rys., tab., wykr.

Twórcy

autor

Pal S.K.

• Center for Soft Computing Research, Indian Statistical Institute, Kolkata, India

autor

Kundu S.

• Center for Soft Computing Research, Indian Statistical Institute, Kolkata, India

autor

Murthy C.A.

• Center for Soft Computing Research, Indian Statistical Institute, Kolkata, India

Bibliografia

• [1] Apache Commons Math (TTest) Documentation.
• [2] Bettini, C., Brdiczka, O., Henricksen, K., Indulska, J., Nicklas, D., Ranganathan, A., Riboni, D.: A survey of context modelling and reasoning techniques, Pervasive and Mobile Computing, 6(2), 2010, 161–180.
• [3] Brézillon, P.: Context in problem solving: a survey, The Knowledge Engineering Review, 14(01), 1999, 47–80.
• [4] Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2010.
• [5] Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2009.
• [6] Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model, 2010 IEEE International Conference on Data Mining, IEEE, 2010, ISSN 1550-4786.
• [7] Choudhury, M. D., Sundaram, H., John, A., Seligmann, D. D., Kelliher, A.: “Birds of a Feather”: Does User Homophily Impact Information Diffusion in Social Media?, CoRR, abs/1006.1702, 2010.
• [8] Dolecek, L., Shah, D.: Influence in a large society: Interplay between information dynamics and network structure, 2009 IEEE International Symposium on Information Theory, IEEE, June 2009, ISBN 978-1-4244-4312-3.
• [9] Domingos, P., Richardson, M.: Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2001.
• [10] Estevez, P. a., Vera, P., Saito, K.: Selecting the Most Influential Nodes in Social Networks, 2007 International Joint Conference on Neural Networks, August 2007, 2397–2402, ISSN 1098-7576.
• [11] Estevez, P. a., Vera, P., Saito, K.: Selecting the Most Influential Nodes in Social Networks, 2007 International Joint Conference on Neural Networks, IEEE, August 2007, ISBN 978-1-4244-1379-9, ISSN 1098-7576.
• [12] Freeman, L.: Centrality in social networks conceptual clarification, Social networks, 1(3), 1979, 215–239, ISSN 0378-8733.
• [13] Goldenberg, J., Libai, B., Muller, E.: Talk of the network: A complex systems look at the underlying process of word-of-mouth, Marketing Letters, 12(3), 2001, 211–223, ISSN 0923-0645.
• [14] Goldenberg, J., Libai, B., Muller, E.: Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata, Academy of Marketing Science Review, 9(3), 2001, 1–18.
• [15] Goyal, A., Lu, W., Lakshmanan, L.: CELF++: optimizing the greedy algorithm for influence maximization in social networks, Proceedings of the 20th international conference companion on World wide web, ACM, 2011.
• [16] Granovetter, M.: Threshold models of collective behavior, The American Journal of Sociology, 83(6), 1978, 1420–1443, ISSN 0002-9602.
• [17] Jeong, H., Albert, R.: Diameter of the world-wide web, Nature, 401(September), 1999, 398–399.
• [18] Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD’03, ACM Press, New York, New York, USA, 2003, ISBN 1581137370.
• [19] Kimura, M., Saito, K.: Tractable Models for Information Diffusion in Social Networks, Principles of Data Mining and Knowledge Discovery, 2006.
• [20] Leskovec, J., Adamic, L. a., Huberman, B. a.: The dynamics of viral marketing, ACM Transactions on the Web, 1(1), May 2007, 5–es, ISSN 15591131.
• [21] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2007.
• [22] Leskovec, J., Lang, K., Dasgupta, A., Mahoney, M.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Mathematics, 6(1), 2009, 29–123.
• [23] McCarthy, J.: Notes on formalizing context, Proceedings of the 13th international joint conference on Artifical Intelligence - Volume 1, Morgan Kaufmann Publishers Inc., Chambery, France, 1993.
• [24] Narayanam, R., Narahari, Y.: A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks, IEEE Transactions on Automation Science and Engineering, 8(1), 2011, 130–147.
• [25] Nieminen, J.: On the Centrality in a Graph, Scandinavian Journal of Psychology, 15, September 1974, 332–336.
• [26] Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’02, 2002, 61.
• [27] Rogers, E. M.: Diffusion of Innovations, The Free Press of Glencoe, New York, 1962.