Documentation for multiplexcd

Functions to perform multiplex community detection.

This module provides functions to simultaneously analyze the community structure common to a list of igraph.Graph instances. It works by performing spectral partitions of a multiplex modularity matrix, which is formed by a block-diagonal arrangement of modularity matrices from each graph and sparse off-diagonal entries that serve as the links between different networks in the multiplex structure. It refines these partitions with a Kernighan-Lin algorithm and by ensuring the connectivity of each community. Networks may be symmetric, directed, or bipartite. Weighted and unweighted networks are both supported.

This module relies on the igraph package for python. With igraph installed, an analysis of one symmetric and one directed graph might proceed as follows:

g = igraph.Graph()
h = igraph.Graph(directed=True)

g_vertex_names = ['a', 'b', 'c', 'd', 'e']
h_vertex_names = ['a', 'b', 'c', 'd', 'e', 'f']

g_edges = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'd'),
           ('d', 'e')]
h_edges = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'a'),
           ('c', 'b'), ('d', 'e'), ('d', 'f'), ('e', 'f'),
           ('e', 'd'), ('f', 'd'), ('f', 'e')]

g.add_vertices(g_vertex_names)
h.add_vertices(h_vertex_names)

g.add_edges(g_edges)
h.add_edges(h_edges)

omega = 1.0
net_list = [g, h]
net_types = ['s', 'd']

community_ids = multiplexcd.multiplex_leading_eigenvector(
                    net_list, omega, net_types)

To measure the multiplex modularity of an arbitrary community id vector:

g.vs['memb'] = [0, 0, 0, 1, 1]
h.vs['memb'] = [0, 0, 0, 1, 1, 1]

community_ids = g.vs['memb'] + h.vs['memb']

B, mu = multiplexcd.get_modularity_matrix(
                    net_list, omega, net_types)

Q = multiplexcd.multiplex_modularity(B, mu, community_ids)

The sets of vertices in each network may differ.

For bipartite networks, the vertices must be sorted by type so that the block-diagonal portions of the network’s adjacency matrix are all 0.

To alter the size of the communities returned by the algorithm, each Graph instance may be assigned its own ‘resolution’ attribute as follows:

gamma_g, gamma_h = 1.0, 1.5
g['resolution'] = gamma_g
h['resolution'] = gamma_h

where gamma_g and gamma_h modify the penalty for grouping unconnected vertices in the same community. Higher values yield smaller communities.

Functions

multiplexcd.multiplex_leading_eigenvector(net_list, w, net_types, weight=’weight’, id_attr=’name’, verbose=False)

Partitions vertices from multiple networks into communities.

Detect communities using a multiplex adaptation of Newman’s (2006) leading eigenvector method.

Args:
net_list (list): Contains igraph.Graph instances. Each graph may have a
‘resolution’ attribute, which defaults to 1.0 if not specified. The multislice network jointly defined by the graphs and the w parameters should have exactly one component.

w: Float or dictionary of the form:

{(i, j): interslice_weight for i, j in itertools.permutation(range(len(net_list)), 2)}
net_types (list): Contains strings specifying the modularity equation

to use for each Graph instance in net_list. Can include:

's' -- symmetric
'd' -- directed
'b' -- bipartite
weight (str): Attribute specifying edge weight. Defaults to ‘weight’.
Use None to specify using edge count.
id_attr (str): Attribute for matching vertex identities across slices.
Defaults to ‘name’.
Returns:
list. Community ids of each vertex.
multiplexcd.get_modularity_matrix(net_list, w, net_types, weight=’weight’, id_attr=’name’)

Get a modularity matrix from a list of networks.

Calculates the modularity matrix for a group of multiplex networks. Networks can be either weighted or unweighted and symmetric, directed, and bipartite. Bipartite graphs require that vertices are sorted by type, and thus that all edges are observed on the off-diagonal blocks of the adjacency matrix.

Args:
net_list (list): Contains igraph.Graph instances. Each graph may have a
‘resolution’ attribute, which defaults to 1.0 if not specified. The multislice network jointly defined by the graphs and the w parameters should have exactly one component.

w: Float or dictionary of the form:

{(i, j): interslice_weight for i, j in itertools.permutation(range(len(net_list)), 2)}
net_types (list): Contains strings specifying the modularity equation

to use for each Graph instance in net_list. Can include:

's' -- symmetric
'd' -- directed
'b' -- bipartite
weight (str): Attribute specifying edge weight. Defaults to ‘weight’.
Use None to specify using edge count.
id_attr (str): Attribute for matching vertex identities across slices.
Defaults to ‘name’.
Returns:
scipy.sparse.csr_matrix. A modularity matrix composed of block-diagonal modularity matrices specific to each network type and manually specified links across networks. float. A measure of multislice strength.
multiplexcd.multiplex_modularity(B, mu, membership)

Calculates a multiplex modularity score.

Calculates the modularity from a given modularity matrix and membership vector.

Args:
B (scipy.sparse.csr_matrix): An n by n sparse modularity matrix where
n is the number of vertices across all networks.

mu (float): The total multislice strength (see Mucha et al. 2010).

membership (list): A vector of community ids of length n.

Returns:
float. The modularity value.
multiplexcd.KL_refinement(B, membership, mu, verbose=False)

Improves a given two-way partition using the KL algorithm.

Searches for higher-modularity partitions by switching each vertex once in the order of the change in modularity resulting from the move. For larger sets of networks with a total of over 10,000 vertices, the algorithm will cease searching for a better partition after 2000 failed attempts.

Args:
B (scipy.sparse.csr_matrix): An n by n sparse modularity matrix where
n is the number of vertices across all networks.

membership (list): A vector of community ids of length n.

mu (float): The total multislice strength (see Mucha et al. 2010).

Returns:
Refined community membership list of length N if successful, otherwise the bool False
multiplexcd.make_multislice_graph(net_list, w)

Makes a multislice representation of a list of separate networks.

Creates a single network object representing the specified multislice structure. Every vertex appears once for each network where it is present. Multislice connections occur between different instances of each vertex across networks as specified by w.

Args:
net_list (list): Contains igraph.Graph instances. Each graph may have a
‘resolution’ attribute, which defaults to 1.0 if not specified. The multislice network jointly defined by the graphs and the w parameters should have exactly one component.

w: Float or dictionary of the form:

{(i, j): interslice_weight for i, j in
itertools.permutation(range(len(net_list)), 2)}
Returns:
igraph.Graph. Represents the combined multislice network. Each vertex enters the multislice network once for each network in which it appears. All edges are undirected and indicate either an observed tie or a specified connection between the same vertex in different network slices.

References

Barber, Michael J. “Modularity and community detection in bipartite networks.”
Physical Review E 76.6 (2007): 066102.
Leicht, Elizabeth A., and Mark EJ Newman. “Community structure in directed
networks.” Physical Review Letters 100.11 (2008): 118703.
Mucha, Peter J., et al. “Community structure in time-dependent, multiscale,
and multiplex networks.” Science 328.5980 (2010): 876-878.
Newman, Mark EJ. “Modularity and community structure in networks.”
PNAS 103.23 (2006): 8577-8582.