Signed networks are a way to represent relationships between entities. These types of networks are called ‘signed’ because the connections between entities are signed: they can be positive (or cooperative) or negative (or conflicting). Community detection in signed networks aims to identify groups of nodes that share similar connection patterns. In this tutorial, we will guide you through applying two popular community detection algorithms to signed networks, using Python.

Algorithms

We will be using two algorithms:

• Spinglass: This algorithm leverages a spin model metaphor to partition nodes into communities. It considers both the weights and signs of connections.
• SPONGE: This spectral clustering technique identifies communities by analyzing the eigenvectors of the signed adjacency matrix.

They are implemented in Python. First, you need install the necessary libraries (pandas is not strictly necessary to implement the algorithms, but we’ll use it throught the tutorial).

pip install igraph
pip install git+https://github.com/alan-turing-institute/SigNet.git 
pip install pandas

Once installed, you can import the libraries and start working with the algorithms.

import igraph as ig
from signet.cluster import Cluster 
import pandas as pd

Construct and visualize a signed network from data

To begin, we’ll construct an example network. This network will be constructed from a series of signed interactions among agents: the edgelist. We can use pandas to read the edgelist from a file or from a list of tuples. In this network, 1 means a positive interaction, and -1 means a negative interaction.

edgelist = [('A', 'B', 1),
            ('A', 'C', -1),
            ('B', 'C', -1) ]

# create DataFrame using edgelist
edgelist_df = pd.DataFrame(edgelist, columns =['source', 'target', 'weight'])

To construct the signed network, we use igraph. In the network, the nodes (agents) will be A, B, C, and the edges (interactions) are the ones listed in the edgelist -with their corresponding weights.

g = ig.Graph.TupleList(edgelist_df.itertuples(index=False), directed=False, weights=False, edge_attrs="weight")

ig.summary(g)

IGRAPH UNW- 3 3 -- 
+ attr: name (v), weight (e)

Then, we can plot our network, still using igraph.

# color the edges based on their weight
g.es["color"] = ["#00BFB3" if edge['weight'] >0  else "#F05D5E"
                 for edge in g.es]
ig.plot(g, vertex_color="grey", edge_color=g.es["color"], edge_width=5, vertex_label=g.vs["name"])

Detect communities

Spinglass

The community-spinglass method is a community detection approach grounded in statistical mechanics. Initially proposed by Reichardt and Bornholdt for unsigned networks, it was later extended by Traag and Bruggeman later extended to signed networks. This algorithm is implemented in the igraph package.

spinglass = g.community_spinglass(weights="weight", spins=50, gamma= 0.5, lambda_= 0.5, implementation='neg')
for i, node in enumerate(g.vs):
    print(f'node {node["name"]}: community {spinglass.membership[i]}') 

node A: community 0
node B: community 0
node C: community 1

Changing the parameters gamma and lambda_ gives more or less importance to positive or negative ties within a community, depending on whether we want agents with negative interactions to be found in the same group of agents.

SPONGE

The SPONGE method (Signed Positive Over Negative Generalized Eigenproblem), introduced by Cucuringu et al. (2019) is based on minimizing the number of violations. These “violations” consist of positive edges between communities and negative edges within communities. An open-source Python implementation of the SPONGE algorithm is available on GitHub.

# get the adjacency matrix of the network (only signs, not weights)
A = g.get_adjacency_sparse(attribute='weight').sign()
c = Cluster((A.multiply(A>0), -A.multiply(A<0)))
sponge = c.SPONGE(k=2)

node A: community 0
node B: community 0
node C: community 1

Changing the parameter k, you can set as many communities as you want.

Conclusion

This tutorial has equipped you with the knowledge and code to apply two common community detection algorithms – Spinglass and SPONGE – to signed networks using Python libraries like igraph and signet. Applying these algorithms, you can gain insights into the underlying community structure of signed networks.

As you saw, there are some parameter choices to be done. We found that changing parameters can drastically influence the results of the algorithms (i.e., find communities where there are none, or just not look for what you wanted to find.). We suggest you to check our last pre-print Community detection in bipartite signed networks is highly dependent on parameter choice and the related code to discover more about the parameter tuning in the case of two-mode (bipartite) signed networks.

If you are doing similar work and you have a different method, let us know! In addition, if you have further questions about community detection, or you think we can help you, do not hesitate to contact us!

References

1. Reichardt, Jörg, and Stefan Bornholdt. “Statistical Mechanics of Community Detection.” Physical Review E, vol. 74, no. 1, July 2006. Crossref, https://doi.org/10.1103/physreve.74.016110.
2. Traag, V. A., and Jeroen Bruggeman. “Community Detection in Networks with Positive and Negative Links.” Physical Review E, vol. 80, no. 3, Sept. 2009. Crossref, https://doi.org/10.1103/physreve.80.036115.
3. Cucuringu, Mihai, et al. “SPONGE: A Generalized Eigenproblem for Clustering Signed Networks.” arXiv, 2019, https://arxiv.org/abs/1904.08575
4. Candellone, Elena, et al. “Community Detection in Bipartite Signed Networks is Highly Dependent on Parameter Choice.” arXiv, 2024, https://arxiv.org/abs/2405.08203