Sergio Gómez - DEIM

Radatools

Communities detection in complex networks and other tools

Index

Description
Main programs
Complete list
Download
Installation
References
History
Authors

Description

Radatools is a set of freely distributed programs to analyze Complex Networks. In particular, it includes programs for Communities Detection, Mesoscales Determination, calculation of Network Properties, and general tools for the manipulation of Networks and Partitions. There are also several programs not strictly related with networks, standing out one for Agglomerative Hierarchical Clustering using Multidendrograms and Binary Dendrograms.

Radatools is just a set of binary executable programs whose source code is available in Radalib. Radalib is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation.

Main programs

The main programs included in the current version of Radatools are:

Communities_Detection:
Community detection in Complex Networks by optimization of modularity. It is prepared to work with:
- unweighted [1] and weighted [2] networks
- undirected [1] and directed [3] networks
- positive [1] and signed [4] networks
- bipartite positive [5] and signed networks
Implements several algorithms for the optimization of modularity [1]:
- exhaustive search
- tabu search [6]
- extremal optimization [7]
- spectral optimization [8]
- fast algorithm [9]
- louvain algorithm [10]
- fine-tuning by reposition
- fine-tuning by bootstrapping based on tabu search [6]
These heuristics may also be combined to obtain the best results.
It is possible to add a common self-loop to all nodes to analyze the communities at any resolution level [6].
Please be kind to cite the corresponding articles when you use these tools.
Mesoscales_Detection:
Implements the strategy in [6,11] for the determination of the community structure of complex networks at different resolution levels, thus finding the whole mesoscale, from all nodes in one community (macroscale) to every node forming its own community (microscale). It is based on the addition of a common self-loop to all nodes, and the optimization of modularity [1,2,3] using the same heuristics as in Communities_Detection.
Network_Properties:
Calculate many global, nodes and edges properties of a network:
- Global: connectedness (weak or strong), degrees and strengths (total, average, maximum and minimum), asymmetry, reciprocity, average entropy,, assortativity (Pearson and Spearman) and estimated error, average clustering coefficient, average path length, diameter and efficiency
- Nodes: degree, strength, entropy, clustering, path length (average and maximum),efficiency and betweenness
- Edges: betweenness
- Distributions: degree (PDF and CCDF)
- Distances: between all pairs of nodes
It works with weighted and unweighted, directed and undirected, positive and signed networks.
Compare_Partitions:
Calculate similarity and dissimilarity indices between two partitions:
- Counters: number of pairs, agreements, and disagreements
- Similarity indices: Jaccard, Rand, adjusted Rand, Fowlkes Mallows, normalized mutual information, and asymmetric Wallace index
- Dissimilarity indices: Mirkin, van Dongen, and variation of information metrics, and their normalized versions
Hierarchical_Clustering:
Agglomerative Hierarchical Clustering with Multidendrograms and Binary Dendrograms, for distances and similarities. The main characteristics are:
- Hierarchical Clustering algorithms: weighted and unweighted variable-group versions of Single Linkage, Complete Linkage, Arithmetic Linkage (UPGMA), Versatile Linkage, Centroid, Ward and Beta Flexible.
- For Binary Dendrograms, in case of ties, many dendrograms may exist, and this tool can enumerate or count them all, or choose the one with maximum cophenetic correlation
- Multidendrograms solve this non-uniqueness problem generating always a unique dendrogram [12]
- Includes Versatile Linkage, a family of space-conserving strategies [13]
Please cite reference [12,13] when you use this tool.
See also mdendro, a package for the R language, and MultiDendrograms, an open source and multiplatform application to build and plot Multidendrograms, with graphical user interface.

Complete list

The complete list of programs included in the current version of Radatools is organized in the following folders:

Communities_Detection:
- Communities_Detection
  Community detection in complex networks by optimization of modularity, using the following heuristics: (h) exhaustive, (t) tabu, (e) extremal, (s) spectral, (f) fast, (l) louvain, (r) reposition, (b) bootstrapping based on tabu.
- Mesoscales_Detection
  Mesoscales detection in complex networks by optimization of modularity for variable common self-loops
- Mesoscales_Fine_Tuning
  Fine Tuning of the mesoscales obtained with Mesoscales_Detection
Communities_Tools:
- Communities_Network
  Given a network and a community, returns the weighted network of communities
- Compare_Partitions
  Calculate similarity and dissimilarity indices between two partitions
- Convert_Clu_To_Lol
  Convert a partition in Pajek format (*.clu) into a partition in our Lol format
- Convert_Lol_To_Clu
  Convert a partition in our Lol format into a partition in Pajek format (*.clu)
- Modularity_Calculation
  Calculate the modularity of a partition of a network, detailing the contributions of individual nodes and communities
- Reformat_Partitions
  Reformat partitions in Pajek and Lol formats changing nodes' indices by nodes' names
- Size_Reduction
  Elimination of simple and triangular 'hairs' of a network to speed-up modularity optimization
- Size_Reduction_Lol_Expand
  Convert a partition of a sized reduced network into a partition of the original network
Data:
- Data_Statistics
  Calculate statistics of rows or columns in a data file
- Data_To_Correlations
  Calculate the correlations network of a data file
- Data_To_Proximities
  Calculate many types of proximities (distances or similarities) between rows or columns in a data file
- Hierarchical_Clustering
  Agglomerative hierarchical clustering with multidendrograms and binary dendrograms
Network_Properties:
- Connected_Subgraphs
  Split a network into its (weak or strong) connected components
- Links_Info
  Calculate the degrees and strengths of the nodes attached to each link in a network
- Network_Properties
  Calculate many properties of a network, including connectedness, degrees, strengths, clustering coefficients, assortativities, path lengths, efficiencies, diameters, entropies and betweenness. Handles all kinds of networks, even weighted, directed and signed
Network_Tools:
- Extract_Subgraphs
  Create subgraphs of a graph
- List_To_Net
  Convert a network in list format to Pajek format (*.net)
- Matrix_To_List
  Convert a matrix to list format
- Matrix_To_Net
  Convert a network in matrix format to Pajek format (*.net)
- Multiplex_Aggregate
  Calculate the aggregate network of a multiplex network
- Multiplex_Extract_Layers
  Extract the layers of a multiplex network
- Net_To_List
  Convert a network in Pajek format (*.net) to list format
- Net_To_Matrix
  Convert a network in Pajek format (*.net) to matrix format
- Sort_Nodes
  Sort nodes of a network randomly or according to degree
- Spanning_Tree
  Calculate the minimum and maximum spanning tree of a graph
- Symmetrize_Network
  Symmetrization of a directed graph

Download

Windows 32 and 64 bits: radatools-5.2-win32.zip
Linux 64 bits: radatools-5.2-linux64.tar.gz
Mac OS X: radatools-5.2-mac.tar.gz
README: txt, pdf
CHANGES: txt, pdf
USAGE: txt, pdf
LICENSE: txt, pdf
INFO-MODULARITIES: pdf
Source code: see Radalib

Installation

No installation needed, just uncompress the downloaded file. See the README and USAGE files for some information to run each program.

References

[1]	M.E.J. Newman and M. Girvan Finding and evaluating community structure in networks Physical Review E 69 (2004) 026113

[2]	M.E.J. Newman Analysis of weighted networks Physical Review E 70 (2004) 056131

[3]	Alex Arenas, Jordi Duch, Alberto Fernández and Sergio Gómez Size reduction of complex networks preserving modularity New Journal of Physics 9 (2007) 176 (pdf) (doi) (IOP open access)

[4]	Sergio Gómez, Pablo Jensen and Alex Arenas Analysis of community structure in networks of correlated data Physical Review E 80 (2009) 016114 (pdf) (doi) (APS)

[5]	Alex Arenas, Alberto Fernández, Santo Fortunato and Sergio Gómez Motif-based communities in complex networks Journal of Physics A: Mathematical and Theoretical 41 (2008) 224001 (pdf) (doi) (IOP)

[6]	Alex Arenas, Alberto Fernández and Sergio Gómez Analysis of the structure of complex networks at different resolution levels New Journal of Physics 10 (2008) 053039 (pdf) (doi) (IOP open access)

[7]	Jordi Duch and Alex Arenas Community detection in complex networks using extremal optimization Physical Review E 72 (2005) 027104 (doi) (APS)

[8]	M.E.J. Newman Modularity and community structure in networks Proc. Nat. Acad. Sci. USA 103 (2006) 8577

[9]	M.E.J. Newman Fast algorithm for detecting community structure in networks Physical Review E 69 (2004) 066133

[10]	V.D. Blondel, J.-L. Guillaume, R.Lambiotte and E. Lefebvre Fast unfolding of communities in large networks Journal of Statistical Mechanics: Theory and Experiment 101 (2008) P10008

[11]	Clara Granell, Sergio Gómez and Alex Arenas Mesoscopic analysis of networks: applications to exploratory analysis and data clustering Chaos 21 (2011) 016102 (pdf) (doi) (AIP)

[12]	Alberto Fernández and Sergio Gómez Solving non-uniqueness in agglomerative hierarchical clustering using Multidendrograms Journal of Classification 25 (2008) 43-65 (view) (pdf) (doi) (Springer)

[13]	Alberto Fernández and Sergio Gómez Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering Journal of Classification 37 (2020) 584�597 (view) (pdf) (doi) (Springer)

History

Radatools 5.2:

minor updates and bug fixes

Radatools 5.1:

added Weighted_Bipartite_Path_Motif and Weighted_Bipartite_Path_Signed modularities

Radatools 5.0:

Communities_Detection and Mesoscales_Detection:
- extremely improved performance of all heuristics
- new heuristics: louvain algorithm
- added initialization modes to heuristics: best, previous, default, together, isolated
- spectral optimization now deals with directed networks
- reposition heuristics now available not just for fine-tuning, similar to louvain
- improved interplay between original self-loops of the network and resolution
Mesoscales_Detection:
- improved automatic detection of minimum resolution for weighted signed modularity
Hierarchical_Clustering:
- added Versatile_Linkage, Geometric_Linkage, Harmonic_Linkage and Beta_Flexible
- Versatile_Linkage and Beta_Flexible depend on a parameter
- weighted or unweighted is selected separately from the clustering method
- Arithmetic_Linkage replaces Unweighted_Average and Weighted_Average
- Centroid replaces Unweighted_Centroid and Weighted_Centroid
Data_Statistics:
- added Kendall tau correlation
Network_Properties:
- performance improved
README:
- many improvements, including indications for the selection of heuristics
many minor updates and bug fixes

Radatools 4.1:

Communities_Detection: improved performance of extremal optimization

Radatools 4.0:

source code available, see Radalib
added program for agglomerative hierarchical clustering: Hierarchical_Clustering
added program to calculate proximity matrices: Data_To_Proximities
added program to calculate correlation matrices: Data_To_Correlations
added program to calculate the network of communities: Communities_Network
added program to obtain some information of each link: Links_Info
added program to aggregate a multiplex network: Multiplex_Aggregate
added program to extract the layers of a multiplex network: Multiplex_Extract_Layers
added program to symmetrize a directed network: Symmetrize_Network
added program to sort the nodes of a network: Sort_Nodes
added conversion programs: Matrix_To_List, Net_To_List
added program to calculate elementary data statistics: Data_Statistics
Mesoscales_Search renamed to Mesoscales_Detection
Network_Properties: faster implementation of edge betweenness
expanded functionality of:
- Communities_Detection
- Compare_Partitions
- Connected_Subgraphs
- Mesoscales_Detection
- Modularity_Calculation
- Network_Properties
minor updates

Radatools 3.2:

added program to calculate the modularity: Modularity_Calculation
expanded functionality of Network_Properties
minor updates

Radatools 3.1:

added program to extract a subgraph from a network: Extract_Subgraphs

Radatools 3.0:

available also for MacOS X
new modularity type: Weighted_Link_Rank
communities detection:
- new implementation of the fast algorithm
mesoscales search updated:
- extended to all modularity types, for self-loops in given range
- automatic determination of self-loops range for Weighted_Signed and Weighted_Newman
connected components:
- now available the calculation of both weak and strong connected components
new programs:
- Size_Reduction, Size_Reduction_Lol_Expand, Convert_Clu_To_Lol, Network_Properties, Compare_Partitions, Spanning_Tree, Net_To_Matrix
list of available programs:
- 01-Prepare_Network: List_To_Net, Matrix_To_Net, Connected_Subgraphs, Size_Reduction
- 02-Find_Communities: Communities_Detection, Mesoscales_Search, Mesoscales_Fine_Tuning
- 03-Reformat_Results: Size_Reduction_Lol_Expand, Convert_Lol_To_Clu, Convert_Clu_To_Lol, Reformat_Partitions
- 04-Other_Tools: Network_Properties, Compare_Partitions, Spanning_Tree, Net_To_Matrix

Radatools 2.1:

minor updates

Radatools 2.0:

added programs for mesoscale search and fine-tuning
adaptated Reformat_Partitions to deal with mesoscales files
list of available programs
- 01-Prepare_Network: List_To_Net, Matrix_To_Net, Connected_Subgraphs
- 02-Find_Communities: Communities_Detection, Mesoscales_Search, Mesoscales_Fine_Tuning
- 03-Reformat_Results: Convert_Lol_To_Clu, Reformat_Partitions

Radatools 1.1:

available also for Linux 32 (compatible with Linux 64)
minor updates

Radatools 1.0:

available only for Windows 32 (compatible with Windows 64)
first release, with programs
- 01-Prepare_Network: List_To_Net, Matrix_To_Net, Connected_Subgraphs
- 02-Find_Communities: Communities_Detection
- 03-Reformat_Partition: Convert_Lol_To_Clu, Reformat_Partition

Authors

Sergio Gómez:

Dept. Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Tarragona, Spain
(web) (email) (ORCID) (Google Scholar) (GitHub) (Twitter)

Alberto Fernández:

Dept. Enginyeria Química, Universitat Rovira i Virgili, Tarragona, Spain
(email) (ORCID) (Google Scholar) (GitHub)