Contribution to community discovery in complex networks

Abstract

Complex networks are the sets made up of a large number of entities interconnected by links. They can be found in several areas: biology, transport, online social networks, agriculture, etc. Many recent applications handle huge volumes of personal or public data resulting from complex networks. They are modeled by graphs inwhich nodes represent entities and edges model the links between them. These entities generally tend to group themselves into communities, based on certain criteria of similarity or connectivity, and this is a very current research problematic called "community detection". A plethora of community detection methods have been implemented. However, many of them consider that communities should be dense and therefore do not take into account the interest that might bind entities within a community. Nevertheless, when interest is taken into account, it is based on semantic. In spite of its usefulness in the interpretation of data, semantic has the main drawback that the network should be known in advance before being exploited. This consideration is not trivial given the immense size of complex networks. Thus, a fundamental aspect remains to be considered, namely the interest based on topology which does not require a prior knowledge of the entire network. The work of research presented in thismanuscript addresses directed, attributed and multidimensional graphs and proposes methods for detecting communities of interest. These methods rely on the topology and properties of real networks to extract significant communities of interest depending on the context. Thus, we propose in the first contribution, a triad-based method for detecting communities of interest in oriented networks, using a seed-centric approach. Indeed, triads constitute a more significant elementary topological structure than structures centered around an actor and a diad, because it offers more configurations. Hence, we define a similarity measure allowing to implement the interest of the incoming links with regard to the outgoing ones, with the result that the communities obtained are dense in triads. This density reflects the idea that nodes of the same community adhere to the strong opinion of the previously identified nodes of interest. The second contribution proposes a hybrid community detection method based on the optimization of a novel quality function, the hybrid modularity. This method is applied to attributed networks to extract communities of interest that are topologically similar and homogeneous in their attributes. In this respect, we propose the hybrid modularity which is a composite modularity combining Newman’s classical modularity and a modularity based on the attributes and orientation of the links through the previous similarity measure. Through this hybrid method, link density is not guaranteed, but the interest in topological equivalence and attribute homogeneity is ensured. Finally, for the case of multidimensional graphs modeling more types of interactions between two entities, we propose in the third contribution a method for identifying communities whose interest is modeled by the level of activity of a node in a dimension. These methods are based on machine learning techniques. Our algorithms, implemented on examples of context graphs, confirm their relevance by extracting groups of more homogeneous entities by common topological features.