Chromatic Community Structure Detection
Détection de Structures Communautaires Chromatiques
Abstract
The detection of community structure is probably one of the hottest trends in complex network research as it reveals the internal organization of people, molecules or processes behind social, biological or computer networks\dots The issue is to provide a network partition representative of this organization so that each community presumably gathers nodes sharing a common mission, purpose or property.
Usually the identification is based on the difference between the connectivity density of the interior and the boundary of a community. Indeed, nodes sharing a common purpose or property are expected to interact closely. Although this rule appears mostly relevant, some fundamental scientific problems like disease module detection highlight the inability to determine significantly the communities under this connectivity rule. The main reason is that the connectivity density is not correlated to a shared property or purpose. Therefore, another paradigm is required for properly formalize this issue in order to meaningfully detect these communities. In this article we study the community formation from this new principle. Considering colors formally figures the shared properties, the issue is thus to maximize group of nodes with the same color within communities.. We study this novel community framework by introducing new measurement called 'chromarity' assessing the quality of the community structure regarding this constraint. Next we propose an algorithm solving the community structure detection based on this new community formation paradigm.
La détection de la structure de la communauté est probablement l’un des sujets les plus en vogue dans les réseaux complexes car elle révèle l’organisation interne des personnes, des molécules ou des processus derrière les réseaux sociaux, biologiques ou informatiques. L’enjeu est de fournir une partition réseau représentative de cette organisation afin que chaque communauté regroupe des nœuds partageant une mission commune, un but ou une propriété.
L’identification est souvent fondée sur la différence entre la densité de connectivité de l’intérieur et la frontière d’une communauté. En effet, les nœuds partageant un objectif ou une propriété commune sont censés interagir étroitement. Bien que cette règle semble souvent pertinente, certains problèmes scientifiques fondamentaux tels que la détection des modules de maladies mettent en évidence l’incapacité de déterminer de manière significative les communautés adoptant cette règle de connectivité. La raison principale est que la densité de connectivité n’est pas corrélée à une propriété ou à un objectif partagé. Par conséquent, un autre paradigme est nécessaire pour formaliser correctement cette question afin de détecter ces communautés avec pertinence. Dans cet article, nous étudions la formation de la communauté à partir de ce nouveau principe. En considérant que les couleurs représentent formellement les propriétés partagées, l’enjeu est donc de maximiser le groupe de nœuds de même couleur au sein de chaque communauté. Nous étudions ce nouveau cadre communautaire en introduisant une nouvelle mesure appelée « chromarité » évaluant la qualité de la structure communautaire par rapport à cette contrainte. Ensuite, nous proposons un algorithme résolvant la détection de la structure communautaire basée sur ce nouveau paradigme de formation de communautés.
Origin : Files produced by the author(s)