Conference article  Open Access

Eva: Attribute-Aware Network Segmentation

Citraro S., Rossetti G.

Computer Science - Social and Information Networks  Physics - Physics and Society  community discovery  68R10 

Identifying topologically well-defined communities that are also homogeneous w.r.t. attributes carried by the nodes that compose them is a challenging social network analysis task. We address such a problem by introducing Eva, a bottom-up low complexity algorithm designed to identify network hidden mesoscale topologies by optimizing structural and attribute-homophilic clustering criteria. We evaluate the proposed approach on heterogeneous real-world labeled network datasets, such as co-citation, linguistic, and social networks, and compare it with state-of-art community discovery competitors. Experimental results underline that Eva ensures that network nodes are grouped into communities according to their attribute similarity without considerably degrading partition modularity, both in single and multi node-attribute scenarios.

Source: International Conference on Complex Networks and their Applications, pp. 141–151, Lisbona, 10-12/12/2019

Publisher: Springer, Berlin , Germania


[2] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of statistical mechanics: theory and experiment, vol. 2008, no. 10, p. P10008, 2008.
[3] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore, “Automating the construction of internet portals with machine learning,” Information Retrieval, vol. 3, pp. 127-163, Jul 2000.
[4] J. Leskovec and J. J. Mcauley, “Learning to discover social circles in ego networks,” in Advances in Neural Information Processing Systems, pp. 539-547, 2012.
[5] J. Neville, D. Jensen, L. Friedland, and M. Hay, “Learning relational probability trees,” in Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, pp. 625- 630, ACM, 2003.
[6] A. Trask, P. Michalak, and J. Liu, “sense2vec - A fast and accurate method for word sense disambiguation in neural word embeddings,” CoRR, vol. abs/1511.06388, 2015.
[7] A. L. Traud, P. J. Mucha, and M. A. Porter, “Social structure of facebook networks,” CoRR, vol. abs/1102.2166, 2011.
[8] V. A. Traag, L. Waltman, and N. J. van Eck, “From louvain to leiden: guaranteeing well-connected communities,” CoRR, vol. abs/1810.08473, 2018.
[9] S. Fortunato and M. Barthelemy, “Resolution limit in community detection,” Proceedings of the national academy of sciences, vol. 104, no. 1, pp. 36-41, 2007.
[10] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the National Academy of Sciences, vol. 105, no. 4, pp. 1118-1123, 2008.
[11] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in largescale networks,” Physical review E, vol. 76, p. 036106, Sep 2007.
[12] T. A. Dang and E. Viennet, “Community detection based on structural and attribute similarities,” International Conference on Digital Society (ICDS), 2012.
[13] I. Falih, N. Grozavu, R. Kanawati, and Y. Bennani, “Community detection in attributed network,” in Companion Proceedings of the The Web Conference 2018, pp. 1299-1306, 2018.
[14] J. Neville, M. Adler, and D. Jensen, “Clustering relational data using attribute and link information,” in 18th International Joint Conference on Artificial Intelligence, pp. 9-15, 2003.
[15] Y. Zhou, H. Cheng, and J. X. Yu, “Graph clustering based on structural/attribute similarities,” Proc. VLDB Endow., vol. 2, pp. 718-729, Aug. 2009.
[16] D. Combe, C. Largeron, M. Géry, and E. Egyed-Zsigmond, “I-louvain: An attributed graph clustering method,” in Advances in Intelligent Data Analysis XIV, (Cham), pp. 181-192, Springer International Publishing, 2015.
[17] I. Falih, N. Grozavu, R. Kanawati, and Y. Bennani, “Anca : Attributed network clustering algorithm,” in Complex Networks & Their Applications VI, (Cham), pp. 241-252, Springer International Publishing, 2018.
[18] H. Elhadi and G. Agam, “Structure and attributes community detection: Comparative analysis of composite, ensemble and selection methods,” in Proceedings of the 7th Workshop on Social Network Mining and Analysis, SNAKDD '13, pp. 10:1-10:7, ACM, 2013.
[19] J. Yang, J. McAuley, and J. Leskovec, “Community detection in networks with node attributes,” in 2013 IEEE 13th International Conference on Data Mining, pp. 1151-1156, Dec 2013.
[20] G. Rossetti, L. Milli, and R. Cazabet, “Cdlib: a python library to extract, compare and evaluate communities from complex networks,” Applied Network Science, vol. 4, no. 1, p. 52, 2019.

Back to previous page
Projects (via OpenAIRE)

SoBigData Research Infrastructure

BibTeX entry
	title = {Eva: Attribute-Aware Network Segmentation},
	author = {Citraro S. and Rossetti G.},
	publisher = {Springer, Berlin , Germania},
	doi = {10.1007/978-3-030-36687-2_12},
	booktitle = {International Conference on Complex Networks and their Applications, pp. 141–151, Lisbona, 10-12/12/2019},
	year = {2020}