TitleAnalysis of On-line Social Networks Represented as Graphs – Extraction of an Approximation of Community Structure Using Sampling
Publication TypeConference Paper
Year of Publication2012
AuthorsArqué NMartínez, Nettleton DF
EditorV. al. Tet
Conference NameMDAI 2012
Conference LocationGirona, Catalunya.
Date Published21/11/2012

In this paper we benchmark two distinct algorithms for extracting community structure from social networks represented as graphs, considering how we can representatively sample an OSN graph while maintaining its community structure. We also evaluate the extraction algorithms’ optimum value (modularity) for the number of communities using five well-known benchmarking datasets, two of which represent real online OSN data. Also we consider the assignment of the filtering and sampling criteria for each dataset. We find that the extraction algorithms work well for finding the major communities in the original and the sampled datasets. The quality of the results is measured using an NMI (Normalized Mutual Information) type metric to identify the grade of correspondence between the communities generated from the original data and those generated from the sampled data. We find that a representative sampling is possible which preserves the key community structures of an OSN graph, significantly reducing computational cost and also making the resulting graph structure easier to visualize. Finally, comparing the communities generated by each algorithm, we identify the grade of correspondence.