RGraph

This package includes the RGraph libraries, the C libraries for complex network analysis developed by Roger Guimera. Some executables, built from the libraries, are also included.

Installation

For the libraries to compile, you will NEED TO INSTALL, first:

1. The GNU Scientific Libraries (GSL)

2. The libtool package is also needed.

Unix

In a Unix-like system, you can install the RGraph libraries and the executables by uncompressing the tarball (tar -xzvf rgraph-version.tar.gz) and running the usual stuff from the rgraph-version directory:

cd rgraph-version

./autogen.sh   # Only needed if you are building from the github source code

./configure

For MAC versions, if an error appears saying that it couldn't find the GSL libraries, execute the ./configure command like that:

LDFLAGS="-L/usr/local/lib" CPPFLAGS="-I/usr/local/include" ./configure

make

[make install]

(In a Windows system, you will first need to install some sort of "Unix emulation." I have successfully compiled the libraries using either Cygwin or MinGW. See below for Windows installation steps).

This will install the libraries in your_default_lib_directory/rgraph and the executables in your_default_bin_directory. To install in a different directory run

./configure --prefix=path_to_install_directory

instead of just ./configure. For other configure options run:

./configure -h

You can uninstall the whole thing by running make uninstall from the installation directory.

You can also test that everything is working by running make check from the installation directory.

Windows (MinGW)

1 First of all, you have to download and install MinGW

During the installation, when it prompts you the packages to install, select gcc, msys and mingw base. The other default options are OK.

2 Download GNU Scientific Libraries GSL. In my installation, I've used version 1.15.

3 Launch MinGW console (Programs -> MinGW -> MinGW Shell or C:\MinGW\msys\1.0\msys).

4 Unzip the contents of the GSL downloaded file under your msys home which is at C:\MinGW\msys\1.0\home\user\ (it's important to perform step 3 or you won't have the home directory).

5 In your msys console, cd into the gsl-15 folder and type the following:

./configure --prefix=/MinGW #path of MinGW installation

make

make install

All this steps may take a while.

6. Untar the contents of rgraph under your msys home and type the following:

./autogen.sh

./configure

make

[make install]

7. To check it's working, use make check command or try to execute any of the executables generated by the make command (for example ./netcarto/netcarto).

Usage

librgraph

librgraph is the library itself. You can use it to build your own network analysis programs. Sorry, as of now no documentation is available, but you may want to take a look at the header files and try to figure things out.

netcarto

Given a network, the program netcarto identifies modules ---i.e. densely connected groups of nodes in the network--- and classifies nodes according to their roles, as defined in Guimera (2005).

In case you use the results of the program in a publication, please cite the following papers:

Guimera, R. & Amaral, L.A.N., Functional cartography of complex metabolic networks, Nature 433, 895-900 (2005).

Guimera, R. & Amaral, L.A.N., Cartography of complex networks: modules and universal roles, J. Stat. Mech.-Theory Exp., art. no. P02001 (2005).

Important note about the new implenentation

In fall 2015 we added a new, equivalent implementation of the simulated annealing algorithm based on adjacency arrays. This new implementation is faster and can treat weighted and unweighted graphs seamlessly. However it has been less tested yet. If correctness is crucial, we encourage you to verify your results with the previous implementation accessible with the netcarto-legacy command. Please report us all bugs or unexpected behavior, it will be greatly appreciated.

Input parameters

The synopsis of the command is:

Usage:
	netcarto [-f FILE] [-o FILE] [-s SEED] [-i ITER] [-c COOL] [-wmr]
	netcarto [-f FILE] [-o FILE] [-s SEED] [-i ITER] [-c COOL] [-wmr] -b [-t]
	netcarto [-f FILE] [-o FILE] [-p FILE] [-w]
	netcarto [-f FILE] [-o FILE] [-p FILE] [-w] -b [-t]
	netcarto  -h
Arguments:
	 -f FILE: Input network file name (default: '-', standard input),
	 -o FILE: Output file name (default: '-', standard output),
	 -s SEED: Random number generator seed (positive integer, default 1111),
	 -i ITER: Iteration factor (recommended 1.0, default 1.0),
	 -c COOL: Cooling factor (recommended 0.950-0.995, default 0.97),
	 -p FILE: Partition file name to load and compute modularity and roles onto, 
	 -w : Read edge weights from the input's third column and uses the weighted modularity,
	 -b : Use bipartite modularity,
	 -r : Compute modularity roles,
	 -t : [with -b only] Find modules for the second column (default: first),
	 -h : Display this synopsis.

• Seed for the random number generator (-s): Must be a positive integer. Since the module identification algorithm is stochastic, different runs will yield, in general, slightly different different modules. Two runs with the same seed, though, should give the exact same results.

• Name of the network file (-f): Name of the file that contains the network. The file must be a list of links with the format:

  n1 n2
  n3 n4
  .  .
  .  .
  .  .

This represents a network with a link between nodes n1 and n2, another between nodes n3 and n4, and so on. Nodes must be separated by spaces.

If you use the weighted definition of modularity (with the -w flag), the file must contain an additional third column giving the weight of each link:

     n1 m1 w1
     n2 m2 w2
      .  .  .
      .  .  .
      .  .  .

• Iteration factor (-i): At each temperature of the simulated annealing (SA), the program performs fN^2 individual-node updates (involving the movement of a single node from one module to another) and fN collective updates (involving the merging of two modules and the split of a module). The number "f" is the iteration factor. Large values of f (1 or larger) will result, in general, in better results (higher modularities) and longer execution times. The recommended range for f is [0.1, 1], although smaller values may be needed for large and/or dense networks. Note, also, that a minimum number of iterations is imposed at each temperature, so that when f is very small, the minimum number will be used instead of fN^2 or fN.

• Cooling factor (-c): After the desired number of updates is done at a certain temperature T, the system is cooled down to a new temperature T'=cT, where c is the cooling factor. the cooling factor must be strictly larger than 0 and strictly smaller than 1. In general, values close to one will result in better results and longer execution times. Recommended values of the cooling factor f are [0.990, 0.999], although smaller values (0.95 or even 0.9) may be needed for large and/or dense networks.

• Compute modularity roles (-r): If this flag is specified, the program will compute for each node the connectivity (within-module z-score of edge weights) and participation coefficient (evenness of linked modules). Those two values are used to give the modularity role of the nodes. Nodes with a low connectivity (<2.5) are classified between ultra peripherals (R1), peripheral (R2), connectors (R3) or kinless (R4) according to their increasing participation coefficient. Nodes with high connectivity are classified as peripheral (R5), connectors (R6) or kinless (R7) hubs. Note that with the -b flag (denoting bipartite networks), those roles are computed on the projected graph.

Netcarto can treat bipartite graphs in a different way if you use the -b flag. It will produce a partition of one of the side according to their shared neighbors. Please refer to (and cite) those article for more information (unweighted and weighted formula respectively):

Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Module identification in bipartite and directed networks, Phys. Rev. E 76, 036102 (2007)

Stouffer, D.B., Sales-Pardo, M., Sirer, M.I. & Bascompte J., Evolutionary conservation of species' roles in food webs, Science 335, 1489-1492 (2012).

• Bipartite -b: This flag sepcifies that the input graph is bipartite. The two component of the bipartite network must be on different columns. If the same name is used in both columns, it will spawn two nodes (one in each component).

• Invert -t: If this flag is specified the program will identify modules in the first second column of the input file.

Program output

After entering these parameters, the algorithm will start to identify the modules in the network. As the SA proceeds, the program displays three columns (in the standard error stream), which indicate the the temperature, the modularity at that temperature, and the stopping criterion (current streak of steps without significant increase in modularity), respectively. This provides you with a fast way to check if the process is too slow or, conversely, if it is fast and the accuracy can be increased. If you want to hide those information you can redirect the error stream:

bipartmod_cl -f network.dat 2> /dev/null

Then come the main program output (in the standard outpu