Entropic Detection of Chromatic Community Structures

The detection of community structure is probably one of the central challenges in complex networks whose objective is to identify internal organizations of people, molecules or processes within a network. 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, this identification is based on the difference in connectivity density between the interior and border 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 meaningfully determine the communities by this connectivity rule. The main reason is that the connectivity density may not be correlated to a shared property or purpose. Another paradigm is therefore necessary to properly formalize this problem in order to accurately detect these communities. In this article we propose a new framework to study this novel community formation property. Considering that colors formally represent shared properties, the problem becomes to maximize groups of nodes of the same color within communities. We introduce a new measurement called chromatic entropy assessing the quality of the community structure regarding the color constraint. Next we propose a novel algorithm detecting the community structure based on this new community formation paradigm.