In this paper, we want to study the informative value of negative links in signed complex networks. For this purpose, we extract and analyze a collection of signed networks representing voting sessions of the European Parliament (EP). We first process some data collected by the Vote Watch Europe Website for the whole 7th term (2009-2014), by considering voting similarities between Members of the EP to define weighted signed links. We then apply a selection of community detection algorithms, designed to process only positive links, to these data. We also apply Parallel Iterative Local Search (Parallel ILS), an algorithm recently proposed to identify balanced partitions in signed networks. Our results show that, contrary to the conclusions of a previous study focusing on other data, the partitions detected by ignoring or considering the negative links are indeed remarkably different for these networks. The relevance of negative links for graph partitioning therefore is an open question which should be further explored.
In the complex networks field, works dedicated to signed networks focus only on the clustering problem, as defined by Davis @cite_28 . @all: I'm actually not so sure of that anymore, I must check again. Community detection involves taking link density into account, which is ont considered in the CC problem (cf. the article of Esmailian . Various methods were proposed for this purpose: evolutionary approaches @cite_38 @cite_45 @cite_24 @cite_17 , agent-based systems @cite_33 , matrix transformation @cite_11 , extensions of the Modularity measure @cite_26 @cite_21 @cite_3 @cite_13 @cite_8 , simulated annealing @cite_27 , spectral approaches @cite_1 @cite_35 @cite_36 , particle swarm optimization @cite_2 @cite_44 , and others. Some authors performed the same task on bipartite networks @cite_40 , while others relaxed the clustering problem in order to identify overlapping communities @cite_18 . Although the methods listed here were applied to networks representing very different systems, authors did not investigate the possibility that some alternative versions of the clustering problems were more appropriate to certain data.
@cite_35 @cite_36 @cite_3 @cite_44 @cite_2 @cite_38 @cite_18 @cite_8 @cite_21 @cite_17 @cite_26 @cite_28 @cite_27 @cite_40 @cite_33 @cite_1 @cite_24 @cite_45 @cite_13 @cite_11
144379121 1976160665 2055269041 2029289148
In this paper we present an original approach for community detection in complex networks. The approach belongs to the family of seed-centric algorithms. However, instead of expanding communities around selected seeds as most of existing approaches do, we explore here applying an ensemble clustering approach to different network partitions derived from ego-centered communities computed for each selected seed. Ego-centered communities are themselves computed applying a recently proposed ensemble ranking based approach that allow to efficiently combine various local modularities used to guide a greedy optimization process. Results of first experiments on real world networks for which a ground truth decomposition into communities are known, argue for the validity of our approach. Graph clustering has been widely applied in exploring regularities emerging in relational data. Recently, the rapid development of network theory correlates graph clustering with the detection of community structure, a common and important topological characteristic of networks. Most existing methods investigate the community structure at a single topological scale. However, as shown by empirical studies, the community structure of real world networks often exhibits multiple topological descriptions, corresponding to the clustering at different resolutions. Furthermore, the detection of multiscale community structure is heavily affected by the heterogeneous distribution of node degree. It is very challenging to detect multiscale community structure in heterogeneous networks. In this paper, we propose a novel, unified framework for detecting community structure from the perspective of dimensionality reduction. Based on the framework, we first prove that the well-known Laplacian matrix for network partition and the widely-used modularity matrix for community detection are two kinds of covariance matrices used in dimensionality reduction. We then propose a novel method to detect communities at multiple topological scales within our framework. We further show that existing algorithms fail to deal with heterogeneous node degrees. We develop a novel method to handle heterogeneity of networks by introducing a rescaling transformation into the covariance matrices in our framework. Extensive tests on real world and artificial networks demonstrate that the proposed correlation matrices significantly outperform Laplacian and modularity matrices in terms of their ability to identify multiscale community structure in heterogeneous networks. Community detection in signed complex networks is a challenging research problem aiming at finding groups of entities having positive connections within the same cluster and negative relationships between different clusters. Most of the proposed approaches have been developed for networks having only positive edges. In this paper we propose a multiobjective approach to detect communities in signed networks. The method partitions a network in groups of nodes such that two objectives are contemporarily optimized. The former is that the partitioning should have dense positive intra-connections and sparse negative interconnections, the latter is that it should have as few as possible negative intra-connections and positive inter-connections. We show that the concepts of signed modularity and frustration fulfill these objectives, and that the maximization of signed modularity and the minimization of frustration allow to obtain very good solutions to the problem. An extensive set of experiments on both real-life and synthetic signed networks shows the efficacy of the approach. Complex systems in nature and in society are often represented as networks, describing the rich set of interactions between objects of interest. Many deterministic and probabilistic clustering methods have been developed to analyze such structures. Given a network, almost all of them partition the vertices into disjoint clusters, according to their connection profile. However, recent studies have shown that these techniques were too restrictive and that most of the existing networks contained overlapping clusters. To tackle this issue, we present in this paper the Overlapping Stochastic Block Model. Our approach allows the vertices to belong to multiple clusters, and, to some extent, generalizes the well-known Stochastic Block Model [Nowicki and Snijders (2001)]. We show that the model is generically identifiable within classes of equivalence and we propose an approximate inference procedure, based on global and local variational techniques. Using toy data sets as well as the French Political Blogosphere network and the transcriptional network of Saccharomyces cerevisiae, we compare our work with other approaches.