Identifying the Presence of Communities in Complex Networks Through Topological Decomposition and Component Densities

Faraz Zaidi 1, 2 Guy Melançon 2, 1
2 GRAVITE - Graph Visualization and Interactive Exploration
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : The exponential growth of data in various fields such as Social Networks and Internet has stimulated lots of activity in the field of network analysis and data mining. Identifying Communities remains a fundamental technique to explore and organize these networks. Few metrics are widely used to discover the presence of communities in a network. We argue that these metrics do not truly reflect the presence of communities by presenting counter examples. This is because these metrics concentrate on local cohesiveness among nodes where the goal is to judge whether two nodes belong to the same community or vise versa. Thus loosing the overall perspective of the presence of communities in the entire network. In this paper, we propose a new metric to identify the presence of communities in real world networks. This metric is based on the topological decomposition of networks taking into account two important ingredients of real world networks, the degree distribution and the density of nodes. We show the effectiveness of the proposed metric by testing it on various real world data sets.
Type de document :
Communication dans un congrès
EGC 2010, Extraction et Gestion de Connaissance, 2010, Yasmine Hamamat, Tunisia. E-19, RNTI, pp.163-174, 2010
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00538566
Contributeur : Faraz Zaidi <>
Soumis le : vendredi 3 décembre 2010 - 12:35:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : vendredi 4 mars 2011 - 02:34:17

Fichier

EGC2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00538566, version 1

Citation

Faraz Zaidi, Guy Melançon. Identifying the Presence of Communities in Complex Networks Through Topological Decomposition and Component Densities. EGC 2010, Extraction et Gestion de Connaissance, 2010, Yasmine Hamamat, Tunisia. E-19, RNTI, pp.163-174, 2010. 〈inria-00538566〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

119