Evidential community detection using structural and attribute information

Kuang Zhou (1, 2) , Arnaud Martin (2) , Quan Pan (1)

1 School of Automation (Northwestern Polytechnical University)
2 DRUID - Declarative & Reliable management of Uncertain, user-generated Interlinked Data

RÉSUMÉ. L'objectif de la détection de communautés est de créer une partition des sommets, de telle sorte que les communautés soient composées de sommets fortement connectés. Les ap-proches existantes de détection de communautés se concentrent principalement sur la structure topologique du réseau, mais elles ignorent largement les informations disponibles à propos des attributs des noeuds. Dans cet article, une nouvelle appproche de détection de communautés qui utilise à la fois les informations structurelles et d'attributs pour extraire une structure de graphe imprécise, est proposée dans le cadre de la théorie des fonctions de croyance. L'objectif de notre méthode consiste à partitionner les sommets dans différents groupes afin que chaque cluster contienne un sous-graphe connecté densément avec les valeurs de l'attribut homogène. Les résultats expérimentaux montrent l'efficacité de la méthode proposée et montrent qu'elle pourrait améliorer les performances de la détection de communautés où les informations sur les propriétés du graphe sont disponibles en complément avec la structure topologique. ABSTRACT. The goal of community detection is to partition nodes into different small subgroups in such a way that vertices in the same community have strong connections. Existing community detection approaches mainly focus on the topological structure of the network, but ignore the information about node attributes. In this paper, a new Evidential Community detection approach which could utilize both Structural and Attribute information, named ECSA, is proposed using belief functions to extract imprecise graph structure. The goal of our method is to partition vertices into different groups so that each cluster contains a densely connected subgraph with homogeneous attribute values. Experimental results illustrate the effectiveness of the proposed method and show that it could indeed improve the performance of community detection when the information about vertex properties is available together with topological structure.

Mots clés: Détection de communautés; Attributs des noeuds; Communautés imprécises; Fonc-tions de croyance KEYWORDS: Community detection; Node attributes; Imprecise communities; Belief functions

Domaines: Intelligence artificielle [cs.AI]

Kuang Zhou, Arnaud Martin, Quan Pan. Evidential community detection using structural and attribute information. Atelier Réseaux Sociaux et Intelligence Artificielle, Jun 2015, Rennes, France. ⟨10.3166/RIA⟩. ⟨hal-01176326⟩