Effectiveness of the K-core Nodes as Seeds for Influence Maximisation in Dynamic Cascades

AUTHOR(S):

Sarah Elsharkawy, Ghada Hassan, Tarek Nabhan, Mohamed Roushdy

TITLE

Effectiveness of the K-core Nodes as Seeds for Influence Maximisation in Dynamic Cascades

ABSTRACT

Influence maximisation is the problem of finding a small subset of nodes in a social network, known as seed nodes, which could maximise the spread of influence. Identifying seed nodes is of interest for marketing and information dissemination purposes. One of the algorithms used to rank a single node’s influence in the spreading process is the k-core decomposition. Most of the work done in this area had two main limitations: 1) worked with a static graph representation of the social network, and 2) did not tackle the possibility of the k-core being formed as a consequence of the domination of other sources such as the mass media or electronic militias and hence the limited contribution of the k-core in the influence dissemination. In this paper, we investigate the evolution of the k-core influence in dynamic meme cascades and scrutinize the effectiveness of using the k-core nodes for the influence maximisation. We propose a measure to estimate the ability of the k-core to disseminate its influence in dynamic cascades, and another to measure the relative strength of the k-core as an influence source among other sources of influence contributing to the cascade development. Finally, we propose combining the two measures to determine the influence domination of the k-core nodes, and hence the effectiveness of targeting these specific nodes for influence maximization. Using four real-life Twitter datasets, we evaluate the proposed measures. Due to the lack of ground truth about the various influence sources affecting the cascade, we examine the datasets for the existence of spam accounts where spam and electronic militias are one potential type of influence sources. We demonstrate how the spam existence indeed affects the correlation between the inner-most k-core size and the cascade size, and in effect, distorts the traditional evaluation of the k-core nodes as influence maximisers.

KEYWORDS

Influence Maximisation, K-core, Influential Spreaders

REFERENCES

[1] A. Adiga and A. K. Vullikanti. How robust is the core of a network? Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, 8188:541–556, 2013.

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

[3] J. I. Alvarez-Hamelin, L. Dall’Asta, A. Barrat, and A. Vespignani. How the k-core decomposition helps in understanding the internet topology. ISMA Workshop on the Internet Topology, 2006.

[4] J. Berger and K. L. Milkman. What makes online content viral? Journal of Marketing Research, 49(2):192–205, 2012.

[5] K. Bhawalkar, J. Kleinberg, K. L. andTim Roughgarden, and A. Sharma. Preventing unraveling in social networks: The anchored k-core problem. Proceedings of the 39th International Colloquium, Part II, pages 440–451, 2012.

[6] J. Borge-Holthoefer, S. Meloni, B. Gonalves, and Y. Moreno. Emergence of influential spreaders in modified rumor models. Journal of Statistical Physics, 151(1-2):383–393, 1 2013.

[7] J. Borge-Holthoefer, A. Rivero, I. Garca, E. Cauh, A. Ferrer, D. Ferrer, D. Francos, D. Iiguez, M. P. Prez, G. Ruiz, F. Sanz, F. Serrano, C. Vias, A. Tarancn, and Y. Moreno. Structural and dynamical patterns on online social networks: the spanish may 15th movement as a case study. PloS one, 6(8):e23883, 2011.

[8] S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, and E. Shir. A model of internet topology using kshell decomposition. Proceedings of the National Academy of Sciences of the United States of America, 104(27):11150–11154, 2007.

[9] M. Cataldi, L. Di Caro, and C. Schifanella. Emerging topic detection on twitter based on temporal and social terms evaluation. In Proceedings of the Tenth International Workshop on Multimedia Data Mining, MDMKDD ’10, pages 4:1–4:10, New York, NY, USA, 2010. ACM.

[10] D. Centola and M. Macy. Complex contagions and the weakness of long ties. American Journal of Sociology, 113(3):702–734, 2007.

[11] N. Chen. On the approximability of influence in social networks. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, pages 1029–1037, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics.

[12] W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in largescale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pages 1029–1038, New York, NY, USA, 2010. ACM.

[13] W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 2010 IEEE International Conference on Data Mining, ICDM ’10, pages 88–97, Washington, DC, USA, 2010. IEEE Computer Society.

[14] R. Crane and D. Sornette. Robust dynamic classes revealed by measuring the response function of a social system. Proceedings of the National Academy of Sciences, 105(41):15649–15653, 2008.

[15] D. J. Daley and D. G. Kendall. Epidemics and rumors. Nature, 204:225–228, 1964.

[16] P. Domingos and M. Richardson. Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, pages 57–66, New York, NY, USA, 2001. ACM.

[17] S. Dorogovtsev, A. Goltsev, and J. Mendes. k-core organization of complex networks. Physical Review Letters, 96:4, 2006.

[18] L. C. Freeman. Centrality in social networks conceptual clarification. Social Networks, 1(3):215–239, 1979.

[19] C. Giatsidis, D. Thilikos, and M. Vazirgiannis. Evaluating cooperation in communities with the k-core structure. In Proc. Int. Conf. Advances in Social Networks Analysis and Mining, pages 87–93, 2011.

[20] C. Giatsidis, D. M. Thilikos, and M. Vazirgiannis. Evaluating cooperation in communities with the kcore structure. Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, pages 87–93, 2011.

[21] W. GOFFMAN and V. A. NEWILL. Generalization of epidemic theory: An application to the transmission of ideas. Nature, 204:225 – 228, 1964.

[22] S. Gonz´alez-Bail´on, J. Borge-Holthoefer, A. Rivero, and Y. Moreno. The Dynamics of Protest Recruitment through an Online Network. Scientific Reports, 1, 2011.

[23] A. Guille, H. Hacid, C. Favre, and D. A. Zighed. Information diffusion in online social networks: a survey. ACM SIGMOD Record, 42(2):17–28, 2013.

[24] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, pages 137–146, New York, NY, USA, 2003. ACM.

[25] D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. In Proceedings of the 32Nd International Conference on Automata, Languages and Programming, ICALP’05, pages 1127–1138, Berlin, Heidelberg, 2005. Springer-Verlag.

[26] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6:888–893, 2010.

[27] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, pages 420–429, New York, NY, USA, 2007. ACM.

[28] J.-H. Lin, Q. Guo, W.-Z. Dong, L.-Y. Tang, and J.-G. Liu. Identifying the node spreading influence with largest k-core values. Physics Letters A, 378(45):3279 – 3284, 2014.

[29] X. Lu and C. Brelsford. Network structure and community evolution on twitter: Human behavior change in response to the 2011 japanese earthquake and tsunami. 4:6773 EP –, Oct 2014. Article.

[30] A. Montresor, F. De Pellegrini, and D. Miorandi. Distributed k-core decomposition. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’11, pages 207–208, New York, NY, USA, 2011. ACM.

[31] S. Pei and H. A. Makse. Spreading dynamics in complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2013(12):P12002, 2013.

[32] S. Pei, L. Muchnik, J. S. Andrade, Z. Zheng, and H. A. Makse. Searching for superspreaders of information in real-world social media. Scientific Reports, 4, July 2014.

[33] S. Pei, L. Muchnik, J. S. A. Jr., Z. Zheng, and H. A. Makse. Searching for superspreaders of information in real-world social media. Scientific Reports, 4:5547, 2014.

[34] H. Pinto, J. M. Almeida, and M. A. Gonc¸alves. Using early view patterns to predict the popularity of youtube videos. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM ’13, pages 365–374, New York, NY, USA, 2013. ACM.

[35] J. Ratkiewicz, M. Conover, M. Meiss, B. Goncalves, S. Patil, A. Flammini, and F. Menczer. Truthy: mapping the spread of astroturf in microblog streams. Proceedings of the 19th ACM International Conference on Information and Knowledge Management, ACM, pages 249–252, 2011.

[36] M. Richardson and P. Domingos. Mining knowledgesharing sites for viral marketing. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02, pages 61–70, New York, NY, USA, 2002. ACM.

[37] S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269–287, 1983.

[38] E. Stattner and N. Vidot. Social network analysis in epidemiology: Current trends and perspectives. International Conference on Research Challenges in Information Science, pages 1–11, May 2011.

[39] M. Trusov, A. V. Bodapati, and R. E. Bucklin. Determining Influential Users in Internet Social Networks. Journal of Marketing Research, 47(4):643–658, Aug. 2010.

[40] Y.Wang, G. Cong, G. Song, and K. Xie. Communitybased greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, pages 1039–1048, New York, NY, USA, 2010. ACM.

[41] D. Watts, P. Dodds, J. D. served as editor, and T. E. served as associate editor for this article. Influentials, networks, and public opinion formation. Journal of Consumer Research, 34(4):441–458, 2007.

[42] L. Weng, A. Flammini, A. Vespignani, and F. Menczer. Competition among memes in a world with limited attention. Scientific Reports, 2(335), 2012.

[43] S. Wuchty and E. Almaas. Evolutionary cores of domain co-occurrence networks. BMC Evolutionary Biology, 5(24), 2005.

[44] W. Xu, W. Liang, X. Lin, and J. X. Yu. Finding top-k influential users in social networks under the structural diversity model. Information Sciences, 355356:110 – 126, 2016.

[45] Y. Yang, J. Tang, C. W. ki Leung, Y. Sun, Q. Chen, J. Li, and Q. Yang. Rain: Social role-aware information diffusion. In AAAI’15, AAAI’15, 2015.

Cite this paper

Sarah Elsharkawy, Ghada Hassan, Tarek Nabhan, Mohamed Roushdy. (2017) Effectiveness of the K-core Nodes as Seeds for Influence Maximisation in Dynamic Cascades. International Journal of Computers, 2, 187-194