Annals of Computer Science and Information Systems, Volume 15

DOI: http://dx.doi.org/10.15439/2018F201

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 237–243 (2018)

Full text

Abstract. Community detection is a widely discussed topic in network science which allows us to discover detailed information about the connections between members of a given group. Communities play a critical role in the spreading of viruses or the diffusion of information. In \cite{kempe,domingos} Kempe et al. proposed the Independent Cascade Model, defining a simple set of rules that describe how information spreads in an arbitrary network. In the same paper the influence maximization problem is defined. In this problem we are looking for the initial vertex set which maximizes the expected number of the infected vertices. The main objective of this paper is to further improve the efficiency of influence maximization by incorporating information on the community structure of the network into the optimization process. We present different community-based improvements for the infection maximization problem, and compare the results by running the greedy maximization method.

References

1. David Kempe, Jon Kleinberg, and Éva Tardos. 2003. 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). ACM, New York, NY, USA, 137-146. http://dx.doi.org/10.1145/956750.956769
2. Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-174, February 2010. ISSN 03701573. http://dx.doi.org/10.1016/j.physrep.2009.11.002.
3. A. Bóta, A. Pluhár, M. Krész: Approximations of the Generalized Cascade Model. Acta Cybernetica Volume 21 (2013) 37–51. http://dx.doi.org/10.14232/actacyb.21.1.2013.4
4. M. K. A. Bota. A high resolution clique based overlapping community detection algorithm for small world networks. Informatica, 39:177-186, 2015.
5. G. Palla, I. Derényi, I. Farkas, T. Vicsek: Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435 (2005), pp. 814-818 http://dx.doi.org/10.1038/nature03607
6. G. Palla, et al., Directed network modules, New J. Phys. 9 (2007) 186. http://dx.doi.org/10.1088/1367-2630/9/6/186
7. M. Granovetter. Threshold models of collective behavior. Am. J. Sociol, 83:1420-1443, 1978. http://dx.doi.org/10.1080/0022250X.1983.9989941
8. P. Domingos, M. Richardson, Mining the Network Value of Customers, Proc. Seventh ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. (2001) 57-66. http://dx.doi.org/10.1145/502512.502525
9. D. Kempe, J. Kleinberg, E. Tardos, Influential Nodes in a Diffusion Model for Social Networks. Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag (2005) 1127- 1138. http://dx.doi.org/10.1007/11523468_91
10. Wei Chen, Chi Wang and Yajun Wang, 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) 1029-1038. http://dx.doi.org/10.1145/1835804.1835934
11. Srivastava, Ajitesh and Chelmis, Charalampos and Prasanna, Viktor K. (2015) The unified model of social influence and its application in influence maximization. Social Network Analysis and Mining 5(1):66:1-66:15 http://dx.doi.org/10.1007/s13278-015-0305-x
12. J. Leskovec, J. Kleinberg, C. Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations. Proceedings of the1th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM (2005) 177-187 http://dx.doi.org/10.1145/1081870.1081893
13. Jure Leskovec and Andrej Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, http://snap.stanford.edu/data, jun. 2014
14. Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. "Local Higher-order Graph Clustering." In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017. http://dx.doi.org/10.1145/3097983.3098069
15. J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007. http://dx.doi.org/10.1145/1217299.1217301
16. S. Kumar, F. Spezzano, V.S. Subrahmanian, C. Faloutsos. Edge Weight Prediction in Weighted Signed Networks. IEEE International Conference on Data Mining (ICDM), 2016. http://dx.doi.org/10.1109/ICDM.2016.0033
17. Kovács, L., Conceptual Systems and Lexical Networks in the Mental Lexicon, (In Hungarian: Fogalmi rendszerek és lexikai hálózatok a mentális lexikonban) Tinta Konyvkiadó, Budapest, 2013.
18. Szabó Sándor, Zaválnij Bogdán Coloring the nodes of a directed graph Acta Universitatis Sapientiae Informatica 6:(6) pp. 117-131. (2014) http://dx.doi.org/10.2478/ausi-2014-0021
19. Szabó Sándor, Zaválnij Bogdán Coloring the edges of a directed graph Indian Journal of Pure & Applied Mathematics 45:(2) pp. 239-260. (2014) http://dx.doi.org/10.1007/s13226-014-0061-z
20. Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based 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). ACM, New York, NY, USA, 1039-1048. http://dx.doi.org/https://doi.org/10.1145/1835804.1835935
21. Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’09). ACM, New York, NY, USA, 199-208. DOI: https://doi.org/10.1145/1557019.1557047
22. Yuchen Li, Ju Fan, Yanhao Wang, Kian-Lee Tan. 2018. Influence Maximization on Social Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering PP(99):1-1 http://dx.doi.org/10.1109/TKDE.2018.2807843