Abstract
Given a social network, we study the problem of finding \(k\) seeds that maximize the dissemination of information. Based on the principle of homophily, communities play an important role since information can be disseminated to communities via the seeds. We introduce a new mechanism for detecting communities satisfying the pertinent criteria for communities and information dissemination. We demonstrate the effectiveness of our approach by an application of the results for influence maximization.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abello, J., Resende, M.G.C., Sudarsky, S.: Massive quasi-clique detection. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 598–612. Springer, Heidelberg (2002)
Bomze, I., Budinich, M., Pardalos, P., Pelilo, M.: The maximum clique problem. Handbook of Combinatorial Optimization A, pp. 1–74 (1999)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: 16th SIGKDD, pp. 1029–1038 (2010)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: 15th SIGKDD, pp. 199–208. ACM (2009)
Coscia, M., Giannoti, F., Pedreschi, D.: A classification for community discovery methods in complex networks. Journal of Statistical Analysis and Data Mining 47(11), 41–45 (1997)
Domingos, P., Richardson, M.: Mining the network value of customers. In: 7th SIGKDD (2001)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM (1999)
Fortunato, S.: Community detection in graphs. Physical Reports 486, 75–174 (2010)
Goyal, A., f. Bonchi, Lakshmanan, L.: A data-based approach to social influence maximization. In: VLDB (2011)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Ninth SIGKDD, pp. 137–146. ACM (2003)
Leskovec, J., Adamic, L.A., Huberman, B.A.: The dynamics of viral marketing. ACM Transactions on the Web 1(1), 1–39 (2007)
Mathioudakis, M., Bonchi, F., Castillo, C., Gionis, A., Ukkonen, A.: Sparsification of influence networks. In: 17th SIGKDD, pp. 529–537. ACM (2011)
Michael, J.: Labor dispute reconciliation in a forest products manufacturing facility. Forest Products Journal 47(11), 41–45 (1997)
Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of the approximations for maximizing submodular set functions. Mathematical Programming 14, 265–294 (1978)
de Nooy, W., Mrvar, A., Batagelj, V.: Exploratory Social Network Analysis with Pajek. Cambridge University Press, Cambridge, UK (2005)
Pattillo, J., Veremyev, A., Butenko, S., Boginski, V.: On the maximum quasi-clique problem. Discrete Applied Mathematics 161(1), 244–257 (2013)
Pullan, W., Franco, M., Mauro, B.: Cooperating local search for the maximum clique problem. J. Heuristics 17, 181–199 (2011)
Pullan, W., Hoos, H.H.: Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research 25, 159–185 (2006)
Raghavan, U., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76 (2007)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: KDD (2002)
Sozio, M., Gionis, A.: The community-search problem and how to plan a successful cocktail party. In: 16th SIGKDD, pp. 939–948. ACM (2010)
Yang, Z., Fu, A., Xu, Y., Huang, S., Leung, H.: Community based information dissemination. Technical Report, CSE, CUHK (2015). http://www.cse.cuhk.edu.hk/~adafu/paper/cbid.pdf
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Yang, Z., Fu, A.WC., Xu, Y., Huang, S., Leung, H.F. (2015). Community Based Information Dissemination. In: Sharaf, M., Cheema, M., Qi, J. (eds) Databases Theory and Applications. ADC 2015. Lecture Notes in Computer Science(), vol 9093. Springer, Cham. https://doi.org/10.1007/978-3-319-19548-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-19548-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19547-6
Online ISBN: 978-3-319-19548-3
eBook Packages: Computer ScienceComputer Science (R0)