Abstract
In this paper, we present a new Memetic Algorithm for overlapping community detection. We use a link-based clustering approach to detect the communities of edges in complex networks. To assess the quality of our method, we present experimental results for benchmark networks in comparison to other state-of-the-art algorithms. In addition, we present a case study of a co-purchasing product network from a brand-centric point of view to show the real-life utility of this new Memetic Algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The data is available at: http://dx.doi.org/10.6084/m9.figshare.1573032.
- 2.
- 3.
- 4.
- 5.
- 6.
References
Aaker, J.L.: Dimensions of brand personality. Journal of Marketing Research 34(3), 347–356 (1997), http://www.jstor.org/stable/3151897
Adamic, L.A., Glance, N.: The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd international workshop on Link discovery. pp. 36–43. ACM (2005)
Ahn, Y.Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466(7307), 761–764 (2010)
Aloise, D., Cafieri, S., Caporossi, G., Hansen, P., Perron, S., Liberti, L.: Column generation algorithms for exact modularity maximization in networks. Physical Review E 82(4), 046112 (2010)
Barabási, A.L., Frangos, J.: Linked: the new science of networks science of networks. Basic Books (2014)
Bayer, B.E.: Color imaging array (Jul 20 1976), uS Patent 3,971,065
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.U.: Complex networks: Structure and dynamics. Physics reports 424(4), 175–308 (2006)
de Vries, N.J., Carlson, J., Moscato, P.: A data-driven approach to reverse engineering customer engagement models: Towards functional constructs. PloS one 9(7), e102768 (2014)
Evans, T.: Information on Les Miserables network used in Evans and Lambiotte 2010. FigShare (10 2015), http://dx.doi.org/10.6084/m9.figshare.1573032
Evans, T., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Physical Review E 80(1), 016105 (2009)
Fortunato, S.: Community detection in graphs. Physics reports 486(3), 75–174 (2010)
Gabardo, A.C., Lopes, H.S.: Using social network analysis to unveil cartels in public bids. In: Network Intelligence Conference (ENIC), 2014 European. pp. 17–21. IEEE (2014)
Gach, O., Hao, J.K.: A memetic algorithm for community detection in complex networks. In: Parallel Problem Solving from Nature-PPSN XII, pp. 327–336. Springer (2012)
Goldberg, D.E., Holland, J.H.: Genetic algorithms and machine learning. Machine learning 3(2), 95–99 (1988)
Gomez Ravetti, M., Rosso, O.A., Berretta, R., Moscato, P.: Uncovering molecular biomarkers that correlate cognitive decline with the changes of hippocampus? gene expression profiles in alzheimer’s disease. PloS one 5(4), e10153 (2010)
He, D., Jin, D., Chen, Z., Zhang, W.: Identification of hybrid node and link communities in complex networks. Scientific reports 5 (2015)
Holland, J.H.: Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press (1992)
Jebabli, M., Cherifi, H., Cherifi, C., Hamouda, A.: Overlapping community detection versus ground-truth in AMAZON co-purchasing network. In: Yétongnon, K., Dipanda, A. (eds.) 11th International Conference on Signal-Image Technology & Internet-Based Systems, SITIS 2015, Bangkok, Thailand, November 23-27, 2015. pp. 328–336. IEEE Computer Society (2015), http://dx.doi.org/10.1109/SITIS.2015.47
Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11(3), 033015 (2009)
Larish, J.J.: Out of Focus: The story of how Kodak lost its direction. CreateSpace Independent Publishing Platform, Luxembourg (2012)
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6(1), 29–123 (2009)
Ma, L., Gong, M., Liu, J., Cai, Q., Jiao, L.: Multi-level learning based memetic algorithm for community detection. Applied Soft Computing 19, 121–133 (2014)
McAuley, J., Pandey, R., Leskovec, J.: Inferring networks of substitutable and complementary products. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 785–794. ACM (2015)
McAuley, J., Yang, A.: Addressing complex and subjective product-related queries with customer reviews. arXiv preprint arXiv:1512.06863 (2015)
Moscato, P., Cotta, C.: A modern introduction to memetic algorithms. In: Handbook of Metaheuristics, pp. 141–183. Springer (2010)
Naeni, L.M., Berretta, R., Moscato, P.: Ma-net: A reliable memetic algorithm for community detection by modularity optimization. In: Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, Volume 1. pp. 311–323. Springer (2015)
Naeni, L.M., De Vries, N.J., Reis, R., Arefin, A.S., Berretta, R., Moscato, P.: Identifying communities of trust and confidence in the charity and not-for-profit sector: A memetic algorithm approach. In: Big Data and Cloud Computing (BdCloud), 2014 IEEE Fourth International Conference on. pp. 500–507. IEEE (2014)
Neri, F., Cotta, C., Moscato, P.: Handbook of memetic algorithms, vol. 379. Springer (2012)
Newman, M., Barabasi, A.L., Watts, D.J.: The structure and dynamics of networks. Princeton University Press (2006)
Newman, M.E.: The structure and function of complex networks. SIAM review 45(2), 167–256 (2003)
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)
Pastor-Satorras, R., Vespignani, A.: Evolution and structure of the Internet: A statistical physics approach. Cambridge University Press (2007)
Pizzuti, C.: Overlapped community detection in complex networks. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation. pp. 859–866. ACM (2009)
Rees, B.S., Gallagher, K.B.: Overlapping community detection by collective friendship group inference. In: Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on. pp. 375–379. IEEE (2010)
Solé, R.V., Pastor-Satorras, R.: 7 complex networks in genomics and proteomics. Handbook of graphs and networks: From the genome to the internet (2006)
Srivastava, A.: Motif analysis in the amazon product co-purchasing network. CoRR abs/1012.4050 (2010), http://arxiv.org/abs/1012.4050
Swasy, A.: Changing Focus: Kodak and the Battle to Save a Great American Company. Times Business, New York, NY (1997)
Yamazaki, T., Shimizu, N., Kobayashi, H., Yamauchi, S.: Weighted micro-clustering: Application to community detection in large-scale co-purchasing networks with user attributes. In: Bourdeau, J., Hendler, J., Nkambou, R., Horrocks, I., Zhao, B.Y. (eds.) Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11-15, 2016, Companion Volume. pp. 131–132. ACM (2016), http://doi.acm.org/10.1145/2872518.2889406
Acknowledgments
A.C. Gabardo is supported by CNPQ Brazil, scholarship number 204978/2014-9.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Gabardo, A.C., Berretta, R., de Vries, N.J., Moscato, P. (2017). Where Does My Brand End? An Overlapping Community Approach. In: Leu, G., Singh, H., Elsayed, S. (eds) Intelligent and Evolutionary Systems. Proceedings in Adaptation, Learning and Optimization, vol 8. Springer, Cham. https://doi.org/10.1007/978-3-319-49049-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-49049-6_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49048-9
Online ISBN: 978-3-319-49049-6
eBook Packages: EngineeringEngineering (R0)