## 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

### Download all the programs

All the C programs of the textbook are available in the

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 |

NetBunch is Free Software, meaning that all the recipients retain the right to:

- Use the software as they wish, for any purpose
- Study how the software works, and modify it for their needs
- Distribute the software to third parties
- Distribute modified copies of the software to third parties

### License

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

## Graph measures

### betweenness (Betweenness)

** betweenness** - Compute the betweenness centrality of nodes and edges

### 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)

** bet_dependency** - Compute the betweenness dependency of nodes

### 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)

** johnson_cycles** - Enumerate the simple cycles of a graph

### 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)

** clust** - Compute the graph and node clustering coefficients

### 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)

** clust_w** - Compute the graph and node clustering of weighted graphs

### 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)

** gn** - Find communities using the Girvan-Newman algorithm

### SYNOPSIS

`gn`

`graph_in`

### DESCRIPTION

`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)

** cnm** - Find communities using greedy modularity optimisation

### SYNOPSIS

`cnm`

`graph_in`

### DESCRIPTION

`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)

** label_prop** - Find communities using 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)

** components** - Find the connected components of a graph

### 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)

** largest_component** - Find largest connected component of a graph

### SYNOPSIS

`largest_component`

`graph_in`

### DESCRIPTION

`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)

** deg_seq** - Compute the degree sequence of a graph

### SYNOPSIS

`deg_seq`

`graph_in`

### DESCRIPTION

`deg_seq`

computes the degree sequence of `graph_in`.

Back to top

### deg_seq_w (Degree sequence - weighted)

** deg_seq_w** - Compute the degree and strength sequence of a graph

### SYNOPSIS

`deg_seq_w`

`graph_in`

### DESCRIPTION

`deg_seq_w`

computes the degree and the strength sequence of `graph_in`.

Back to top

### fitmle (Fit power-law)

** fitmle** - Fit a set of values with a power-law distribution

### 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.

If `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)

** graph_info** - Print basic information about a graph

### SYNOPSIS

`graph_info`

`graph_in`

### DESCRIPTION

`graph_info`

prints the number of nodes, number of edges, average
degree, and average squared degree of `graph_in`.

Back to top

### modularity (Modularity)

** modularity** - Compute the modularity of a partition of a graph

### SYNOPSIS

`modularity`

`graph_in` `partition`

### DESCRIPTION

`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)

** f3m** - Count all the 3-node subgraphs of a directed graph

### 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)

** knn** - Compute the average nearest neighbours degree function

### 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)

** knn_w** - Compute the weighted average nearest neighbours degree function

### 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)

** node_components** - Find the components associated to a specific node

### 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)

** power_law** - Sample N integers from a discrete power-law distribution

### SYNOPSIS

`power_law`

`gamma` `k_min` `k_max` `N`

### DESCRIPTION

`power_law`

samples `N` elements from the discrete power-law
distribution

```
P(k) ~ k^{gamma}
```

where

```
k_min <= k <= k_max, gamma < 1
```

The program can be used to generate a power-law degree distribution with an assigned value of the exponent <gamma.

Back to top

### pm (Power method)

** pm** - Compute the leading eigenvalue and eigenvector of a graph

### SYNOPSIS

`pm`

`graph_in` `is_dir` `eps`

### DESCRIPTION

`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)

** shortest** - Compute the distance between one node and all the other nodes of a graph

### 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)

** shortest_avg_max_hist** - Compute the distance between one node and all the other nodes of a graph

### SYNOPSIS

`shortest_avg_max_hist`

`graph_in` `node`

### DESCRIPTION

`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)

** dijkstra** - Compute the distance between one node and all the other nodes of a weighted graph

### SYNOPSIS

`dijkstra`

`graph_in` `node`

### DESCRIPTION

`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)

** kruskal** - Find the minimum/maximum spanning tree of a graph

### 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)

** strong_conn** - Find the strongly connected components of a directed graph

### 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)

** ba** - Grow a Barabasi-Albert scale-free random graph

### SYNOPSIS

`ba`

`N` `m` `n0`

### DESCRIPTION

`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)

** conf_model_deg** - Sample a simple graph from the configuration 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)

** conf_model_deg_nocheck** - Sample a multigraph from the configuration model

### SYNOPSIS

`conf_model_deg_nocheck`

`degs`

### DESCRIPTION

`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)

** er_A** - Sample a random graph from the Erdos-Renyi 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)

** er_B** - Sample a random graph from the Erdos-Renyi 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)

** dms** - Grow a scale-free random graph with tunable exponent

### SYNOPSIS

`dms`

`N` `m` `n0` *a*

### DESCRIPTION

`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)

** bb_fitness** - Grow a random graph with the 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
```

where `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)

** bbv** - Grow a weighted scale-free random graph

### SYNOPSIS

`bbv`

`N` `m` `n0` `w0` `delta`

### DESCRIPTION

`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)

** hv_net** - Sample a random graph with an assigned joint degree distribution

### 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)

** ws** - Create a small-world graph using the Watts-Strogatz 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