"""Generators for some simplicial complexes.
All the functions in this module return a SimplicialComplex class.
"""
from collections import defaultdict
from itertools import combinations
import numpy as np
from ..core import SimplicialComplex
from ..utils.utilities import find_triangles
__all__ = [
"random_simplicial_complex",
"random_flag_complex_d2",
"random_flag_complex",
"flag_complex",
"flag_complex_d2",
]
[docs]def random_simplicial_complex(N, ps, seed=None):
"""Generates a random hypergraph
Generate N nodes, and connect any d+1 nodes
by a simplex with probability ps[d-1]. For each simplex,
add all its subfaces if they do not already exist.
Parameters
----------
N : int
Number of nodes
ps : list of float
List of probabilities (between 0 and 1) to create a
hyperedge at each order d between any d+1 nodes. For example,
ps[0] is the wiring probability of any edge (2 nodes), ps[1]
of any triangles (3 nodes).
seed : int, numpy.random.Generator, or None, optional
The seed for the random number generator. By default, None.
Returns
-------
Simplicialcomplex object
The generated simplicial complex
References
----------
Described as 'random simplicial complex' in
"Simplicial Models of Social Contagion", Nature Communications 10(1), 2485,
by I. Iacopini, G. Petri, A. Barrat & V. Latora (2019).
https://doi.org/10.1038/s41467-019-10431-6
Example
-------
>>> import xgi
>>> H = xgi.random_simplicial_complex(20, [0.1, 0.01])
"""
rng = np.random.default_rng(seed)
if (np.any(np.array(ps) < 0)) or (np.any(np.array(ps) > 1)):
raise ValueError("All elements of ps must be between 0 and 1 included.")
nodes = range(N)
simplices = []
for i, p in enumerate(ps):
d = i + 1 # order, ps[0] is prob of edges (d=1)
potential_simplices = combinations(nodes, d + 1)
from scipy.special import comb
n_comb = comb(N, d + 1, exact=True)
mask = rng.random(size=n_comb) <= p # True if simplex to keep
simplices_to_add = [e for e, val in zip(potential_simplices, mask) if val]
simplices += simplices_to_add
S = SimplicialComplex()
S.add_nodes_from(nodes)
S.add_simplices_from(simplices)
return S
[docs]def flag_complex(G, max_order=2, ps=None, seed=None):
"""Generate a flag (or clique) complex from a
NetworkX graph by filling all cliques up to dimension max_order.
Parameters
----------
G : Networkx Graph
max_order : int
maximal dimension of simplices to add to the output simplicial complex
ps: list of float
List of probabilities (between 0 and 1) to create a
hyperedge from a clique, at each order d. For example,
ps[0] is the probability of promoting any 3-node clique (triangle) to
a 3-hyperedge.
seed : int, numpy.random.Generator, or None, optional
The seed for the random number generator. By default, None.
Returns
-------
S : SimplicialComplex
Notes
-----
Computing all cliques quickly becomes heavy for large networks. `flag_complex_d2`
is faster to compute up to order 2.
See also
--------
flag_complex_d2
"""
# This import needs to happen when this function is called, not when it is
# defined. Otherwise, a circular import error would happen.
from ..core import SimplicialComplex
rng = np.random.default_rng(seed)
nodes = G.nodes()
N = len(nodes)
edges = G.edges()
cliques_to_add = _cliques_to_fill(G, max_order)
S = SimplicialComplex()
S.add_nodes_from(nodes)
S.add_simplices_from(edges)
if not ps: # promote all cliques
S.add_simplices_from(cliques_to_add, max_order=max_order)
return S
# store max cliques per order
cliques_d = defaultdict(list)
for x in cliques_to_add:
cliques_d[len(x)].append(x)
# promote cliques with a given probability
for i, p in enumerate(ps[: max_order - 1]):
d = i + 2 # simplex order
cliques_d_to_add = [el for el in cliques_d[d + 1] if rng.random() <= p]
S.add_simplices_from(cliques_d_to_add, max_order=max_order)
return S
[docs]def flag_complex_d2(G, p2=None, seed=None):
"""Generate a flag (or clique) complex from a
NetworkX graph by filling all cliques up to dimension 2.
Parameters
----------
G : networkx Graph
Graph to consider
p2: float
Probability (between 0 and 1) of filling empty triangles in graph G
seed : int, numpy.random.Generator, or None, optional
The seed for the random number generator. By default, None.
Returns
-------
S : xgi.SimplicialComplex
Notes
-----
Computing all cliques quickly becomes heavy for large networks. This
is faster than `flag_complex` to compute up to order 2.
See also
--------
flag_complex
"""
# This import needs to happen when this function is called, not when it is
# defined. Otherwise, a circular import error would happen.
from ..core import SimplicialComplex
rng = np.random.default_rng(seed)
nodes = G.nodes()
edges = G.edges()
S = SimplicialComplex()
S.add_nodes_from(nodes)
S.add_simplices_from(edges)
triangles_empty = find_triangles(G)
if p2 is not None:
triangles = [el for el in triangles_empty if rng.random() <= p2]
else:
triangles = triangles_empty
S.add_simplices_from(triangles)
return S
[docs]def random_flag_complex_d2(N, p, seed=None):
"""Generate a maximal simplicial complex (up to order 2) from a :math:`G_{N,p}`
Erdős-Rényi random graph.
This proceeds by filling all empty triangles in the graph with 2-simplices.
Parameters
----------
N : int
Number of nodes
p : float
Probabilities (between 0 and 1) to create an edge
between any 2 nodes
seed : int, numpy.random.Generator, or None, optional
The seed for the random number generator. By default, None.
Returns
-------
SimplicialComplex
Notes
-----
Computing all cliques quickly becomes heavy for large networks.
"""
if (p < 0) or (p > 1):
raise ValueError("p must be between 0 and 1 included.")
import networkx as nx
G = nx.fast_gnp_random_graph(N, p, seed=seed)
return flag_complex_d2(G)
[docs]def random_flag_complex(N, p, max_order=2, seed=None):
"""Generate a flag (or clique) complex from a
:math:`G_{N,p}` Erdős-Rényi random graph.
This proceeds by filling all cliques up to dimension max_order.
Parameters
----------
N : int
Number of nodes
p : float
Probability (between 0 and 1) to create an edge
between any 2 nodes
max_order : int
maximal dimension of simplices to add to the output simplicial complex
seed : int, numpy.random.Generator, or None, optional
The seed for the random number generator. By default, None.
Returns
-------
SimplicialComplex
Notes
-----
Computing all cliques quickly becomes heavy for large networks.
"""
if (p < 0) or (p > 1):
raise ValueError("p must be between 0 and 1 included.")
import networkx as nx
G = nx.fast_gnp_random_graph(N, p, seed=seed)
nodes = G.nodes()
cliques = _cliques_to_fill(G, max_order)
S = SimplicialComplex()
S.add_nodes_from(nodes)
S.add_simplices_from(cliques, max_order=max_order)
return S
def _cliques_to_fill(G, max_order):
"""Return cliques to fill for flag complexes,
to be passed to `add_simplices_from`.
This function was written to speedup flag_complex functions
by avoiding adding redundant faces.
Parameters
----------
G : networkx Graph
Graph to consider
max_order: int or None
If None, return maximal cliques. If int, return all cliques
up to max_order.
Returns
-------
cliques : list
List of cliques
"""
import networkx as nx
if max_order is None:
cliques = list(nx.find_cliques(G)) # max cliques
else: # avoid adding many unnecessary redundant cliques
cliques = []
for clique in nx.enumerate_all_cliques(G): # sorted by size
if len(clique) == 1:
continue # don't add singletons
if len(clique) <= max_order + 1:
cliques.append(clique)
else:
break # dont go over whole list if not necessary
return cliques
