Book's Programs (NetBunch)
Here you find all the implementation in C language of the algorithms described in the Appendix of the textbook:
For each program you find below a brief description, a set of options, and a link to the manual page, which includes examples about how the program is used.
When run without any argument, each program shows some usage information
All the programs can also be found on GitHub:
https://github.com/KatolaZ/NetBunch
All the C programs of the textbook are available in the
NetBunch is Free Software, meaning that all the recipients retain the right to:
All the programs included in NetBunch can be used,
distributed, and modified under the terms of the GNU General
Public License, either version 3 of the Licence or (at your
option) any later version.
All the programs included in NetBunch are distributed in the
hope that they will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
License for more details.
A copy of the GNU General Public License is included in all
the archive files made available for download. You can also
obtain a copy of the GNU General Public License from at
http://www.gnu.org/licenses/gpl.html
betweenness - Compute the betweenness centrality of nodes and edges
bet_dependency - Compute the betweenness dependency of nodes
johnson_cycles - Enumerate the simple cycles of a graph
clust - Compute the graph and node clustering coefficients
clust_w - Compute the graph and node clustering of weighted graphs
gn - Find communities using the Girvan-Newman algorithm
cnm - Find communities using greedy modularity optimisation
label_prop - Find communities using label propagation
components - Find the connected components of a graph
largest_component - Find largest connected component of a graph
deg_seq - Compute the degree sequence of a graph
deg_seq_w - Compute the degree and strength sequence of a graph
fitmle - Fit a set of values with a power-law distribution
If
graph_info - Print basic information about a graph
modularity - Compute the modularity of a partition of a graph
f3m - Count all the 3-node subgraphs of a directed graph
knn - Compute the average nearest neighbours degree function
knn_w - Compute the weighted average nearest neighbours degree function
node_components - Find the components associated to a specific node
power_law - Sample N integers from a discrete power-law distribution
where The program can be used to generate a power-law degree distribution
with an assigned value of the exponent <gamma.
pm - Compute the leading eigenvalue and eigenvector of a graph
shortest - Compute the distance between one node and all the other nodes of a graph
shortest_avg_max_hist - Compute the distance between one node and all the other nodes of a graph
dijkstra - Compute the distance between one node and all the other nodes of a weighted graph
kruskal - Find the minimum/maximum spanning tree of a graph
strong_conn - Find the strongly connected components of a directed graph
ba - Grow a Barabasi-Albert scale-free random graph
conf_model_deg - Sample a simple graph from the configuration model
conf_model_deg_nocheck - Sample a multigraph from the configuration model
er_A - Sample a random graph from the Erdos-Renyi model A
er_B - Sample a random graph from the Erdos-Renyi model B
dms - Grow a scale-free random graph with tunable exponent
bb_fitness - Grow a random graph with the fitness model
where
bbv - Grow a weighted scale-free random graph
hv_net - Sample a random graph with an assigned joint degree distribution
ws - Create a small-world graph using the Watts-Strogatz model
Download all the programs
Windows (64bit)
netbunch-1.0_win.zip
Mac OS X
netbunch-1.0_mac.zip
Debian/Devuan/Ubuntu (64bit deb)
netbunch_1.0-1_amd64.deb
RedHat/Fedora/CentOS (64bit rpm)
netbunch-1.0-2.x86_64.rpm
Sources (zip)
netbunch-1.0.zip
Sources (tar.gz)
netbunch-1.0.tar.gz
License
Graph measures
betweenness (Betweenness)
SYNOPSIS
betweenness graph_in [ SEQ node_start [node_end]]betweenness graph_in [ RND num]DESCRIPTION
betweenness computes the betweenness centrality of all the nodes and
edges of an undirected graph provided as input. The program implements
the algorithm by U. Brandes, and computes the betweenness using all
the shortest paths originating from a subset of the nodes of the
graph, either in a sequence (if SEQ is the second parameter) or
sampled unirofmly at random (if RND is the second parameter). If
graph_in is the only parameter, betweenness takes into account all
the shortest paths.
Back to top
bet_dependency (Betweenness dependency)
SYNOPSIS
bet_dependency graph_in [ node_start [node_end]]DESCRIPTION
bet_dependency computes the betweenness dependency of all the nodes
of an undirected graph provided as input. The program implements the
algorithm by U. Brandes, and computes the betweenness dependency using
all the shortest paths originating from the subset of the nodes of the
graph whose labels are in the interval [node_start, node_end]. If
node_end is not given, the last label of the graph is assumed. If
node_start is not given, use the shortest paths originating from all
the nodes of the graph.
Back to top
johnson_cycles (Cycles)
SYNOPSIS
johnson_cycles graph_in [max_length [SHOW]]DESCRIPTION
johnson_cycles enumerates all the simple cycles of the graph given
on input, and prints the total number of cycles of each length. If
max_length is provided, johnson_cycles ignores any cycle whose
length is larger than max_length. If SHOW is given as third
argument, all the found cycles are printed on STDERR as soon as they
are found.
Back to top
clust (Clustering)
SYNOPSIS
clust graph_in [SHOW]DESCRIPTION
clust computes the clustering coefficient of the undirected graph
given as input in the file graph_in. If SHOW is provided as a
second parameter, the program prints on STDERR the label, degree, and
clustering coefficient of all the nodes in graph_in.
Back to top
clust_w (Clustering - weighted)
SYNOPSIS
clust_w graph_in [SHOW]DESCRIPTION
clust_w computes the clustering coefficient of the undirected and
weighted graph given as input in the file graph_in. The program uses
the definition of weighted clustering proposed by Barrat, Barthelemy,
Pastor-Satorras ans Vespignani. If SHOW is provided as a second
parameter, the program prints on STDERR the label, degree, and
clustering coefficient of all the nodes in graph_in.
Back to top
gn (Communities - Girvan-Newman)
SYNOPSIS
gn graph_inDESCRIPTION
gn finds the communities in graph_in using the Girvan-Newman
algorithm, based on the successive removal of edges with high
betweenness. The program prints on STDOUT the partition corresponding
to the highest value of the modularity function, and reports on STDERR
the number of communities after each edge removal and the
corresponding value of modularity.N.B.: the program recomputes the edge betweenness of the graph after
the removal of each edge, so it is not feasible to use it on large
graphs.
Back to top
cnm (Communities - greedy modularity)
SYNOPSIS
cnm graph_inDESCRIPTION
cnm finds the communities in graph_in using the greedy modularity
optimisation algorithm proposed by Clauset, Newman and Moore. The
program prints on STDOUT the partition corresponding to the highest
value of the modularity function, and reports on STDERR the number of
communities and the corresponding value of modularity at each
step. The algorithm is quite eficient and thus suitable to find
communities in large graphs.
Back to top
label_prop (Communities - label propagation)
SYNOPSIS
label_prop [SYNC|ASYNC] graph_in [max_epochs]DESCRIPTION
label_prop finds the communities in graph_in using the label
propagation algorithm proposed by Raghavan, Albert, and Kumara. The
program prints on STDOUT the partition obtained where no more label
flips are possible, and reports on STDERR the number of communities
and the corresponding value of modularity at each epoch. When used in
ASYNC mode, the algorithm is suitable to find communities in large
graphs.
Back to top
components (Connected components)
SYNOPSIS
components graph_in [SHOW]DESCRIPTION
components finds the connected components of the undirected graph
given as input using the Depth-First Search algorithm, and prints the
size of each of them. If the optional second parameter SHOW is
provided, the program dumps on output also the list of nodes belonging
to each component.
Back to top
largest_component (Largest component)
SYNOPSIS
largest_component graph_inDESCRIPTION
largest_component computes the largest connected component of
graph_in, and prints on STDOUT the corresponding edge list.
Back to top
deg_seq (Degree sequence)
SYNOPSIS
deg_seq graph_inDESCRIPTION
deg_seq computes the degree sequence of graph_in.
Back to top
deg_seq_w (Degree sequence - weighted)
SYNOPSIS
deg_seq_w graph_inDESCRIPTION
deg_seq_w computes the degree and the strength sequence of graph_in.
Back to top
fitmle (Fit power-law)
SYNOPSIS
fitmle data_in [tol [TEST [num_test]]]DESCRIPTION
fitmle fits the data points contained in the file data_in with a
power-law function P(k) ~ k-gamma, using the Maximum-Likelihood
Estimator (MLE). In particular, fitmle finds the exponent gamma
and the minimum of the values provided on input for which the
power-law behaviour holds. The second (optional) argument tol sets
the acceptable statistical error on the estimate of the exponent.TEST is provided, the program associates a p-value to the
goodness of the fit, based on the Kolmogorov-Smirnov statistics
computed on num_test sampled distributions from the theoretical
power-law function. If num_test is not provided, the test is based
on 100 sampled distributions.
Back to top
graph_info (Graph info)
SYNOPSIS
graph_info graph_inDESCRIPTION
graph_info prints the number of nodes, number of edges, average
degree, and average squared degree of graph_in.
Back to top
modularity (Modularity)
SYNOPSIS
modularity graph_in partitionDESCRIPTION
modularity computes the value of the modularity function associated
to a partition of the nodes of the graph given as input.
Back to top
f3m (Motifs analysis)
SYNOPSIS
f3m graph_in [num_random]DESCRIPTION
f3m performs a motif analysis on graph_in, i.e., it counts all the
3-node subgraphs and computes the z-score of that count with respect
to the corresponding configuration model ensemble.
Back to top
knn (Nearest-neighbour degree)
SYNOPSIS
knn graph_in [NO|LIN|EXP bin_param]DESCRIPTION
knn computes the average nearest neighbours degree function knn(k)
of the graph graph_in given as input. The program can (optionally)
average the results over bins of equal or exponentially increasing
width (the latter is also known as logarithmic binning).
Back to top
knn_w (Nearest-neighbour degree - weighted)
SYNOPSIS
knn_w graph_in [NO|LIN|EXP bin_param]DESCRIPTION
knn_w computes the weighted average nearest neighbours degree
function knn_w(k) of the weighted graph graph_in given as input. The
program can (optionally) average the results over bins of equal or
exponentially increasing width (the latter is also known as
logarithmic binning).
Back to top
node_components (Node components)
SYNOPSIS
node_components graph_in node [component [SHOW]]DESCRIPTION
node_components finds the components associated to the node node
of the graph graph_in provided as input, and prints on output the
size of those components. The value of the third parameter component
can be set to IN, OUT, INOUT, SSC, WCC, or ALL. According
to the value of component, the program will compute the IN-component
(IN), the OUT-component (OUT), both the IN- and OUT-component
(INOUT), the strongly connected components (SCC), or the
weakly-connected component (WCC) to which node belongs. If the
third parameter is omitted or equal to ALL, then node_components
computes all the components associated to node. If SHOW is
specified as the fourth parameter, the program also shows the list of
nodes which belong to each of the required components.
Back to top
power_law (Power-law sequences)
SYNOPSIS
power_law gamma k_min k_max NDESCRIPTION
power_law samples N elements from the discrete power-law
distributionP(k) ~ k^{gamma}
k_min <= k <= k_max, gamma < 1
Back to top
pm (Power method)
SYNOPSIS
pm graph_in is_dir epsDESCRIPTION
pm computes the leading eigenvalue and the corresponding eigenvector
of the matrix given as input, using the Power Method. In particular,
this implementation uses the Rayleigh iteration, which allows faster
convergence on undirected graphs.
Back to top
shortest (Shortest paths)
SYNOPSIS
shortest graph_in node [SHOW]DESCRIPTION
shortest computes the distance (and the shortest paths) between a
given node and all the other nodes of an undirected graph provided as
input. The program implements the Breadth-First Search algorithm.
Back to top
shortest_avg_max_hist (Shortest paths statistics)
SYNOPSIS
shortest_avg_max_hist graph_in nodeDESCRIPTION
shortest_avg_max_hist computes the distance (and the shortest paths)
between a given node and all the other nodes of an undirected graph
provided as input. The program implements the Breadth-First Search
algorithm, and works almost exactly as shortest(1), except for the
output.
Back to top
dijkstra (Shortest paths - weighted)
SYNOPSIS
dijkstra graph_in nodeDESCRIPTION
dijkstra computes the distance (and the shortest paths) between a
given node and all the other nodes of an undirected weighted graph
provided as input. The program implements the Dijkstra's algorithm.
Back to top
kruskal (Spanning trees)
SYNOPSIS
kruskal graph_in [MAX]DESCRIPTION
kruskal computes the minimum (or maximum) spanning tree of
graph_in, using the Kruskal's algorithm. If grahp_in is
unweighted, kruskal computes one of the spanning trees of the
graph. The program prints on output the (weighted) edge list of the
spanning tree.
Back to top
strong_conn (Strongly connected components)
SYNOPSIS
strong_conn graph_in [SHOW]DESCRIPTION
strong_conn finds the strongly connected components of the directed
graph given as input using the Kosaraju-Sharir algorithm, and prints
the size of each of them. If the optional second parameter SHOW is
provided, the program dumps on output also the list of nodes belonging
to each component.
Back to top
Graph models
ba (BA model)
SYNOPSIS
ba N m n0DESCRIPTION
ba grows an undirected random scale-free graph with N nodes using
the linear preferential attachment model proposed by Barabasi and
Albert. The initial network is a ring of n0 nodes, and each new node
creates m new edges. The resulting graph will have a scale-free
degree distribution, whose exponent converges to gamma=3.0 for large
N.
Back to top
conf_model_deg (Conf. model)
SYNOPSIS
conf_model_deg degs [threshold]DESCRIPTION
conf_model_deg samples a simple random undirected graph (i.e., a
graph without self-loops and multiple edges) from the configuration
model associated to the degree sequence provided in the input file
degs.
Back to top
conf_model_deg (Conf. model multigraph)
SYNOPSIS
conf_model_deg_nocheck degsDESCRIPTION
conf_model_deg_nocheck samples an undirected multigraph (i.e., a
graph that might contain self-loops multiple edges) from the
configuration model associated to the degree sequence provided in the
input file degs.
Back to top
er_A (ER model A)
SYNOPSIS
er_A N K [fileout]DESCRIPTION
er_A samples a random graph with N nodes and K edges from the
Erdos-Renyi model A, i.e. the ensemble of random graphs where K links
are placed uniformly at random among N nodes. The program dumps the
edge list of the resulting graph on output. If the optional fileout
is provided, the output is written on a file with that name.
Back to top
er_B (ER model B)
SYNOPSIS
er_B N p [fileout]DESCRIPTION
er_B samples a random graph from the Erdos-Renyi model B, i.e. a
graph with N nodes where each of the <N(N-1)/2> edges is created
independently with probability p. The program dumps the edge list of
the resulting graph on output. If the optional fileout is provided,
the output is written on a file with that name.
Back to top
dms (DMS model)
SYNOPSIS
dms N m n0 aDESCRIPTION
dms grows an undirected random scale-free graph with N nodes using
the modified linear preferential attachment model proposed by
Dorogovtsev, Mendes and Samukhin. The initial network is a clique of
n0 nodes, and each new node creates m new edges. The resulting
graph will have a scale-free degree distribution, whose exponent
converges to gamma=3.0 + a/m for large N.
Back to top
bb_fitness (Fitness model)
SYNOPSIS
bb_fitness N m n0 [SHOW]DESCRIPTION
bb_fitness grows an undirected random scale-free graph with N
nodes using the fitness model proposed by Bianconi and Barabasi. The
initial network is a clique of n0 nodes, and each new node creates
m new edges. The probability that a new node create an edge to node
j is proportional to a_j * k_j
a_j is the attractiveness (fitness) of node j. The values of
node attractiveness are sampled uniformly in the interval [0,1].
Back to top
bbv (Growing weighted graphs)
SYNOPSIS
bbv N m n0 w0 deltaDESCRIPTION
bbv grows an undirected weighted random scale-free graph with N
nodes using the model proposed by Barrat, Barthelemy, and
Vespignani. The initial network is a clique of n0 nodes, and each
new node creates m new edges, each with weight w0. The parameter
delta sets the amount of weight to be redistributed in the
neighbourhood of newly-connected nodes.
Back to top
hv_net (Hidden-variable model)
SYNOPSIS
hv_net graph_in [SHOW]DESCRIPTION
hv_net samples a random graph whose joint degree distribution is
equal to that of another graph provided as input, using the
hidden-variable model proposed by Boguna ans Pastor-Satorras.
Back to top
ws (WS model)
SYNOPSIS
ws N m p [SHOW]DESCRIPTION
ws creates a small-world undirected graph with 'N' nodes using the
Watts-Strogatz small-world network model. The nodes are initially
placed around a circle and each node is connected to its 'm' closest
neighbours on either side. Then, each edge is rewired (independently)
with probability 'p'. The program prints on output the edge-list of
the resulting graph.
Back to top