Entropic Detection of Chromatic Community Structures
Détection entropique de structures communautaires chromatiques
Abstract
The detection of community structure is probably one of the central trends in complex network emphasizing the complex internal organization of people, molecules, or processes behind social, biological or computer networks. . . 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 significantly determine 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 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 chromatic entropy 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 structure communautaires est probablement l'un des sujets chauds dans les réseaux complexes mettant l'accent sur la reconnaissant d’organisations internes complexes de personnes, de molécules ou de processus derrière les réseaux sociaux, biologiques ou informatiques. Le problème est de fournir une partition réseau représentative de cette organisation afin que chaque communauté rassemble des nœuds partageant une mission, un objectif ou une propriété commune. Habituellement, l'identification est basée sur la différence entre la densité de connectivité de l'intérieur et de 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 être pleinement fondée, certains problèmes scientifiques importants tels que la détection des modules de maladie soulignent l'incapacité de déterminer de manière significative les communautés en suivant 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, la recherche d’un autre paradigme devient nécessaire pour formaliser correctement cette question afin de détecter de manière ces communautés significativement. Dans cet article, nous étudions la formation de la communauté à partir de ce nouveau principe. En considérant que les couleurs figurent formellement les propriétés partagées, l'enjeu est donc de maximiser le groupe de nœuds avec la même couleur au sein des communautés. Nous étudions ce nouveau cadre en introduisant une nouvelle mesure appelée entropie chromatique permettant d’évaluer la qualité d’une structure communautaire. Ensuite, nous proposons un algorithme résolvant la détection de structure communautaire basée sur ce nouveau paradigme de formation de communautés colorées.
Origin : Files produced by the author(s)