search.cpan.org is shutting down
Tristan Colombo > BioGraph > BioGraph::Compute
Module Version: 1.0.1

# NAME

BioGraph::Compute

# SYNOPSIS

use Biograph::Compute;

# DESCRIPTION

Package for manipulate graphs represented as well as adjacent matrix or adjacent list. The common format of representation adopted for the graphs files is : number_of_edges on the first line, and then vertice_i \t vertice_j on the other one.

# AVAILABLE FUNCTIONS

This is the list of the differents functions implemented in this library.

vertices_nb

Compute the number of vertices in a graph

• SYNOPSIS \$N=vertices_nb(representation, graph)
• PARAMETERS
representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

graph

the hash table of the graph

• OUTPUT The number of vertices in the graph
edges_nb

Compute the number of edges in a graph

SYNOPSIS \$N=edges_nb(representation, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

graph

the hash table of the graph

OUTPUT The number of edges in the graph

mean

Compute the mean number of a table excluding the null values

SYNOPSIS \$M=mean(table)

PARAMETERS

table

the hash table

OUTPUT The mean number of the table

global_density

Computing of the global density of a graph

SYNOPSIS \$d=densite(representation, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

graph

the hash table of the graph

OUTPUT The density of the graph. (Usefull with the graph with multiple connected components)

degree

Compute the degree of each vertex

SYNOPSIS %D=degree(representation, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

graph

the hash table of the graph

OUTPUT The hash table of each vertice's degree

cluster_coeff

Compute the cluster coefficient of a graph

SYNOPSIS \$C=cluster_coeff(representation, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

graph

the hash table of the graph

OUTPUT Computing of the clustering coefficient defined by Watts and Strogatz ("Collective dynamics of 'small-world' networks", Nature, 393, 440-442 (1998)). Taking two neigbours vertices, this is the probability that a third vertex exists which is neigbour to the two others. C=(Number of neighbours vertices with a third neighbour vertex to the two others)/(Number of neighbour vertices = number of edges)

shortest_paths

Compute the sortest paths in a graph from a given starting vertex

SYNOPSIS %PCC=shortest_paths(representation, start, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

start

start vertex

graph

the hash table of the graph

OUTPUT Computing of the list of the shortest paths from a start vertex in a graph using the Dijkstra's algorithm.

triangle_nb

Compute the number of triangles in which a given edge is implicated

SYNOPSIS %D=triangle_nb(representation, start_vertex, end_vertex, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

start_vertex

first vertex of the edge

end_vertex

second vertex of the edge

graph

the hash table of the graph

OUTPUT The number of triangles in wich the given edge is implicated.

distance

Compute a specific distance between vertices of the graph (distances are Dice, Radicchi, ...)

SYNOPSIS %D=distance(representation, distance, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

distance

a type of distance in :

Betweeness

the betweeness of an edge is the number of shortest paths which going through this edge ; a definition is given by Girvan and Newman in "Community structure in social and biological networks", Proc. Natl. Acad. Sci. USA, 99, 7821-7826 (2002)

Dice

for an edge (i,j), the distance d(i,j) is (nb of triangles in which (i,j) is implicated + 1)/min(degree(i)-1, degree(j)-1). see F. Radicchi, C. Castellano, F. Cecconi, V. Loreto and D. Parisi, "Defining and identifying communities in networks", preprint condmat/0309263 (2003)

All these distances are conform to the specification given previsiously

graph

the hash table of the graph

OUTPUT The table of the distance choosen. Note that the value '32767' indicate infinite distance.

internal_density

Computing of the internal density of a cluster of a graph

SYNOPSIS \$d=internal_density(representation, cluster, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

cluster

the list of vertices of the cluster

graph

the hash table of the graph

OUTPUT The internal density of the given cluster of the graph.

external_density

Computing of the external density of a graph

SYNOPSIS \$d=external_density(representation, nb_cluster, ref_cluster, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

nb_cluster

the number of clusters

ref_cluster

a reference to the list of clusters

graph

the hash table of the graph

OUTPUT The external density of the graph.

maximal_distance

Computing of the maximal distance of a graph

SYNOPSIS \$d=maximal_distance(distance_list)

PARAMETERS

distance_list

hash table of the distances

OUTPUT The maximal distance.

distance2density

Convert a list of edges distances in vertices densities

SYNOPSIS %Dens=distance2density(representation, ref_distances, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

ref_distances

a reference to the list of distances

graph

the hash table of the graph

OUTPUT The list of the densities of each vertex.

edge_density

Convert a list of vertices densities in edges densities

SYNOPSIS %Distance=edge_density(representation, ref_densities, graph)

PARAMETERS

representation

the type of representation choosen : 1 = adjacent matrix, and 2 = adjacent list

ref_densities

a reference to the list of densities

graph

the hash table of the graph

OUTPUT The list of the densities for each edge (expressed as a distance)

```  Graph::Calculs is Copyright (C) 2004, Tristan Colombo
CNRS - LCB, 31 chemin Joseph Aiguier
13009 Marseille
France

Email: tristan.colombo@ibsm.cnrs-mrs.fr