CEMCN 2014 - Special issue on clustering & evolution mining of complex networks

Complex network analysis techniques provide today powerful approaches for gaining deep insights on behaviors of complex systems composed for a high dimensional number of interacting objects. This is already applied to a wide variety of applications including both on-line and off-line social networks, system biology, information retrieval, natural language processing, peer-to-peer networks, direct marketing, recommender systems and much more. There are clear indications that large real-world networks evolve following self-organising principles and evolutionary laws that cross-disciplinary boundaries. Actually, real-world complex networks share a set of topological features that distinguish them from pure random networks. Exhibition of a mesoscopic structure, often denoted by community level, is one of the main characteristics of real-world complex networks. Identifying relevant communities is a central question in various applications: a community can be a set of genes or proteins involved in a biological function, a set of documents or web pages related to a given topic, a set of similar customers or users having a same profile in a social network. Devising efficient algorithms for community detection in very large-scale networks has gained much attention in the last few years. A main trend in this area focuses on detecting disjoint communities, in static networks applying an optimization scheme of a quality function of a graph partition (namely the modularity criteria introduced by Newman). However, recent evolutions argue for renewing the effort in this field. For instance:
- The quick pace of growth of handled networks does not allow considering having a global knowledge about network topology. This makes it hard to evaluate the quality of a partition.
- Recent studies have shown that the modularity suffers from some serious drawbacks including a resolution limit and discernment problem. The first problem refers to incapacity of modularity optimization driven approaches to detect communities whose size is below a given threshold. The second problem refers to the fact that many different partitions of a graph may have a high score in terms of their modularity.
- Almost all studied complex networks are highly dynamic where both nodes and edges can vary with time. Furthermore, in many applications one node may belongs to more than one community at the same time.
Another highly promising research topic concerning large real networks is about modeling their dynamics. Indeed, most often, data about these networks have been collected at different time points. This dynamic view of the system allows the time component to play a key role in the comprehension of the evolution of the network structure and/or of flows within those networks. Time can help to determine the real causal relationships within a network, for a better understanding, for instance, of gene activations within a regulation network, or link creation/deletion within a collaboration network, or else opinion or disease diffusion within a social network. Handling such dynamic data is a also a major challenge for current pluridisciplinary research in particular in machine learning and data mining, and has led to the development of recent innovative techniques that consider complex/multi-level time-evolving networks, graphs, potentially heterogeneous (nodes and links). This special issue also aims at attracting contributions from all aspects of dynamic networks analysis: large real network analysis and modeling, and knowledge discovery within those dynamic networks. A number of works have been proposed recently to handle one or more of these issues. The purpose of this special issue is to provide a review of recent innovative approaches for node clustering and evolution mining in dynamic large-scale complex networks.