"""Generators for classes of graphs used in studying social networks."""
import itertools
import math
import random
import networkx as nx
# Copyright(C) 2011, 2015 by
# Ben Edwards <bedwards@cs.unm.edu>
# Aric Hagberg <hagberg@lanl.gov>
# Konstantinos Karakatsanis <dinoskarakas@gmail.com>
# All rights reserved.
# BSD license.
__author__ = """\n""".join(['Ben Edwards (bedwards@cs.unm.edu)',
'Aric Hagberg (hagberg@lanl.gov)',
'Konstantinos Karakatsanis '
'<dinoskarakas@gmail.com>'])
__all__ = ['caveman_graph', 'connected_caveman_graph',
'relaxed_caveman_graph', 'random_partition_graph',
'planted_partition_graph', 'gaussian_random_partition_graph',
'ring_of_cliques', 'windmill_graph']
def caveman_graph(l, k):
"""Returns a caveman graph of `l` cliques of size `k`.
Parameters
----------
l : int
Number of cliques
k : int
Size of cliques
Returns
-------
G : NetworkX Graph
caveman graph
Notes
-----
This returns an undirected graph, it can be converted to a directed
graph using :func:`nx.to_directed`, or a multigraph using
``nx.MultiGraph(nx.caveman_graph(l, k))``. Only the undirected version is
described in [1]_ and it is unclear which of the directed
generalizations is most useful.
Examples
--------
>>> G = nx.caveman_graph(3, 3)
See also
--------
connected_caveman_graph
References
----------
.. [1] Watts, D. J. 'Networks, Dynamics, and the Small-World Phenomenon.'
Amer. J. Soc. 105, 493-527, 1999.
"""
# l disjoint cliques of size k
G = nx.empty_graph(l * k)
if k > 1:
for start in range(0, l * k, k):
edges = itertools.combinations(range(start, start + k), 2)
G.add_edges_from(edges)
return G
def connected_caveman_graph(l, k):
"""Returns a connected caveman graph of `l` cliques of size `k`.
The connected caveman graph is formed by creating `n` cliques of size
`k`, then a single edge in each clique is rewired to a node in an
adjacent clique.
Parameters
----------
l : int
number of cliques
k : int
size of cliques
Returns
-------
G : NetworkX Graph
connected caveman graph
Notes
-----
This returns an undirected graph, it can be converted to a directed
graph using :func:`nx.to_directed`, or a multigraph using
``nx.MultiGraph(nx.caveman_graph(l, k))``. Only the undirected version is
described in [1]_ and it is unclear which of the directed
generalizations is most useful.
Examples
--------
>>> G = nx.connected_caveman_graph(3, 3)
References
----------
.. [1] Watts, D. J. 'Networks, Dynamics, and the Small-World Phenomenon.'
Amer. J. Soc. 105, 493-527, 1999.
"""
G = nx.caveman_graph(l, k)
for start in range(0, l * k, k):
G.remove_edge(start, start + 1)
G.add_edge(start, (start - 1) % (l * k))
return G
def relaxed_caveman_graph(l, k, p, seed=None):
"""Return a relaxed caveman graph.
A relaxed caveman graph starts with `l` cliques of size `k`. Edges are
then randomly rewired with probability `p` to link different cliques.
Parameters
----------
l : int
Number of groups
k : int
Size of cliques
p : float
Probabilty of rewiring each edge.
seed : int,optional
Seed for random number generator(default=None)
Returns
-------
G : NetworkX Graph
Relaxed Caveman Graph
Raises
------
NetworkXError:
If p is not in [0,1]
Examples
--------
>>> G = nx.relaxed_caveman_graph(2, 3, 0.1, seed=42)
References
----------
.. [1] Santo Fortunato, Community Detection in Graphs,
Physics Reports Volume 486, Issues 3-5, February 2010, Pages 75-174.
https://arxiv.org/abs/0906.0612
"""
if seed is not None:
random.seed(seed)
G = nx.caveman_graph(l, k)
nodes = list(G)
for (u, v) in G.edges():
if random.random() < p: # rewire the edge
x = random.choice(nodes)
if G.has_edge(u, x):
continue
G.remove_edge(u, v)
G.add_edge(u, x)
return G
def random_partition_graph(sizes, p_in, p_out, seed=None, directed=False):
"""Return the random partition graph with a partition of sizes.
A partition graph is a graph of communities with sizes defined by
s in sizes. Nodes in the same group are connected with probability
p_in and nodes of different groups are connected with probability
p_out.
Parameters
----------
sizes : list of ints
Sizes of groups
p_in : float
probability of edges with in groups
p_out : float
probability of edges between groups
directed : boolean optional, default=False
Whether to create a directed graph
seed : int optional, default None
A seed for the random number generator
Returns
-------
G : NetworkX Graph or DiGraph
random partition graph of size sum(gs)
Raises
------
NetworkXError
If p_in or p_out is not in [0,1]
Examples
--------
>>> G = nx.random_partition_graph([10,10,10],.25,.01)
>>> len(G)
30
>>> partition = G.graph['partition']
>>> len(partition)
3
Notes
-----
This is a generalization of the planted-l-partition described in
[1]_. It allows for the creation of groups of any size.
The partition is store as a graph attribute 'partition'.
References
----------
.. [1] Santo Fortunato 'Community Detection in Graphs' Physical Reports
Volume 486, Issue 3-5 p. 75-174. https://arxiv.org/abs/0906.0612
"""
# Use geometric method for O(n+m) complexity algorithm
# partition = nx.community_sets(nx.get_node_attributes(G, 'affiliation'))
if seed is not None:
random.seed(seed)
if not 0.0 <= p_in <= 1.0:
raise nx.NetworkXError("p_in must be in [0,1]")
if not 0.0 <= p_out <= 1.0:
raise nx.NetworkXError("p_out must be in [0,1]")
if directed:
G = nx.DiGraph()
else:
G = nx.Graph()
G.graph['partition'] = []
n = sum(sizes)
G.add_nodes_from(range(n))
# start with len(sizes) groups of gnp random graphs with parameter p_in
# graphs are unioned together with node labels starting at
# 0, sizes[0], sizes[0]+sizes[1], ...
next_group = {} # maps node key (int) to first node in next group
start = 0
group = 0
for n in sizes:
edges = ((u + start, v + start)
for u, v in
nx.fast_gnp_random_graph(n, p_in, directed=directed).edges())
G.add_edges_from(edges)
next_group.update(dict.fromkeys(range(start, start + n), start + n))
G.graph['partition'].append(set(range(start, start + n)))
group += 1
start += n
# handle edge cases
if p_out == 0:
return G
if p_out == 1:
for n in next_group:
targets = range(next_group[n], len(G))
G.add_edges_from(zip([n] * len(targets), targets))
if directed:
G.add_edges_from(zip(targets, [n] * len(targets)))
return G
# connect each node in group randomly with the nodes not in group
# use geometric method like fast_gnp_random_graph()
lp = math.log(1.0 - p_out)
n = len(G)
if directed:
for u in range(n):
v = 0
while v < n:
lr = math.log(1.0 - random.random())
v += int(lr / lp)
# skip over nodes in the same group as v, including self loops
if next_group.get(v, n) == next_group[u]:
v = next_group[u]
if v < n:
G.add_edge(u, v)
v += 1
else:
for u in range(n - 1):
v = next_group[u] # start with next node not in this group
while v < n:
lr = math.log(1.0 - random.random())
v += int(lr / lp)
if v < n:
G.add_edge(u, v)
v += 1
return G
def planted_partition_graph(l, k, p_in, p_out, seed=None, directed=False):
"""Return the planted l-partition graph.
This model partitions a graph with n=l*k vertices in
l groups with k vertices each. Vertices of the same
group are linked with a probability p_in, and vertices
of different groups are linked with probability p_out.
Parameters
----------
l : int
Number of groups
k : int
Number of vertices in each group
p_in : float
probability of connecting vertices within a group
p_out : float
probability of connected vertices between groups
seed : int,optional
Seed for random number generator(default=None)
directed : bool,optional (default=False)
If True return a directed graph
Returns
-------
G : NetworkX Graph or DiGraph
planted l-partition graph
Raises
------
NetworkXError:
If p_in,p_out are not in [0,1] or
Examples
--------
>>> G = nx.planted_partition_graph(4, 3, 0.5, 0.1,seed=42)
See Also
--------
random_partition_model
References
----------
.. [1] A. Condon, R.M. Karp, Algorithms for graph partitioning
on the planted partition model,
Random Struct. Algor. 18 (2001) 116-140.
.. [2] Santo Fortunato 'Community Detection in Graphs' Physical Reports
Volume 486, Issue 3-5 p. 75-174. https://arxiv.org/abs/0906.0612
"""
return random_partition_graph([k] * l, p_in, p_out, seed, directed)
def gaussian_random_partition_graph(n, s, v, p_in, p_out, directed=False,
seed=None):
"""Generate a Gaussian random partition graph.
A Gaussian random partition graph is created by creating k partitions
each with a size drawn from a normal distribution with mean s and variance
s/v. Nodes are connected within clusters with probability p_in and
between clusters with probability p_out[1]
Parameters
----------
n : int
Number of nodes in the graph
s : float
Mean cluster size
v : float
Shape parameter. The variance of cluster size distribution is s/v.
p_in : float
Probabilty of intra cluster connection.
p_out : float
Probability of inter cluster connection.
directed : boolean, optional default=False
Whether to create a directed graph or not
seed : int
Seed value for random number generator
Returns
-------
G : NetworkX Graph or DiGraph
gaussian random partition graph
Raises
------
NetworkXError
If s is > n
If p_in or p_out is not in [0,1]
Notes
-----
Note the number of partitions is dependent on s,v and n, and that the
last partition may be considerably smaller, as it is sized to simply
fill out the nodes [1]
See Also
--------
random_partition_graph
Examples
--------
>>> G = nx.gaussian_random_partition_graph(100,10,10,.25,.1)
>>> len(G)
100
References
----------
.. [1] Ulrik Brandes, Marco Gaertler, Dorothea Wagner,
Experiments on Graph Clustering Algorithms,
In the proceedings of the 11th Europ. Symp. Algorithms, 2003.
"""
if s > n:
raise nx.NetworkXError("s must be <= n")
assigned = 0
sizes = []
while True:
size = int(random.normalvariate(s, float(s) / v + 0.5))
if size < 1: # how to handle 0 or negative sizes?
continue
if assigned + size >= n:
sizes.append(n - assigned)
break
assigned += size
sizes.append(size)
return random_partition_graph(sizes, p_in, p_out, directed, seed)
def ring_of_cliques(num_cliques, clique_size):
"""Defines a "ring of cliques" graph.
A ring of cliques graph is consisting of cliques, connected through single
links. Each clique is a complete graph.
Parameters
----------
num_cliques : int
Number of cliques
clique_size : int
Size of cliques
Returns
-------
G : NetworkX Graph
ring of cliques graph
Raises
------
NetworkXError
If the number of cliques is lower than 2 or
if the size of cliques is smaller than 2.
Examples
--------
>>> G = nx.ring_of_cliques(8, 4)
See Also
--------
connected_caveman_graph
Notes
-----
The `connected_caveman_graph` graph removes a link from each clique to
connect it with the next clique. Instead, the `ring_of_cliques` graph
simply adds the link without removing any link from the cliques.
"""
if num_cliques < 2:
raise nx.NetworkXError('A ring of cliques must have at least '
'two cliques')
if clique_size < 2:
raise nx.NetworkXError('The cliques must have at least two nodes')
G = nx.Graph()
for i in range(num_cliques):
edges = itertools.combinations(range(i * clique_size, i * clique_size +
clique_size), 2)
G.add_edges_from(edges)
G.add_edge(i * clique_size + 1, (i + 1) * clique_size %
(num_cliques * clique_size))
return G
def windmill_graph(n, k):
"""Generate a windmill graph.
A windmill graph is a graph of `n` cliques each of size `k` that are all
joined at one node.
It can be thought of as taking a disjoint union of `n` cliques of size `k`,
selecting one point from each, and contracting all of the selected points.
Alternatively, one could generate `n` cliques of size `k-1` and one node
that is connected to all other nodes in the graph.
Parameters
----------
n : int
Number of cliques
k : int
Size of cliques
Returns
-------
G : NetworkX Graph
windmill graph with n cliques of size k
Raises
------
NetworkXError
If the number of cliques is less than two
If the size of the cliques are less than two
Examples
--------
>>> G = nx.windmill_graph(4, 5)
Notes
-----
The node labeled `0` will be the node connected to all other nodes.
Note that windmill graphs are usually denoted `Wd(k,n)`, so the parameters
are in the opposite order as the parameters of this method.
"""
if n < 2:
msg = 'A windmill graph must have at least two cliques'
raise nx.NetworkXError(msg)
if k < 2:
raise nx.NetworkXError('The cliques must have at least two nodes')
G = nx.disjoint_union_all(itertools.chain([nx.complete_graph(k)],
(nx.complete_graph(k - 1)
for _ in range(n - 1))))
G.add_edges_from((0, i) for i in range(k, G.number_of_nodes()))
return G