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
- Radicchi
-
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)
AUTHOR AND COPYRIGHT
Graph::Calculs is Copyright (C) 2004, Tristan Colombo
CNRS - LCB, 31 chemin Joseph Aiguier
13009 Marseille
France
Email: tristan.colombo@ibsm.cnrs-mrs.fr
All rights reserved.
You may distribute this package under the terms of either the GNU
General Public License or the Artistic License, as specified in the
Perl README file.
39 POD Errors
The following errors were encountered while parsing the POD:
- Around line 158:
Expected text after =item, not a bullet
- Around line 162:
Expected text after =item, not a bullet
- Around line 178:
Expected text after =item, not a bullet
- Around line 243:
Expected text after =item, not a bullet
- Around line 247:
Expected text after =item, not a bullet
- Around line 259:
Expected text after =item, not a bullet
- Around line 301:
Expected text after =item, not a bullet
- Around line 305:
Expected text after =item, not a bullet
- Around line 321:
Expected text after =item, not a bullet
- Around line 358:
Expected text after =item, not a bullet
- Around line 362:
Expected text after =item, not a bullet
- Around line 378:
Expected text after =item, not a bullet
- Around line 438:
Expected text after =item, not a bullet
- Around line 442:
Expected text after =item, not a bullet
- Around line 458:
Expected text after =item, not a bullet
- Around line 533:
Expected text after =item, not a bullet
- Around line 537:
Expected text after =item, not a bullet
- Around line 557:
Expected text after =item, not a bullet
- Around line 683:
Expected text after =item, not a bullet
- Around line 687:
Expected text after =item, not a bullet
- Around line 711:
Expected text after =item, not a bullet
- Around line 776:
Expected text after =item, not a bullet
- Around line 780:
Expected text after =item, not a bullet
- Around line 816:
Expected text after =item, not a bullet
- Around line 949:
Expected text after =item, not a bullet
- Around line 953:
Expected text after =item, not a bullet
- Around line 973:
Expected text after =item, not a bullet
- Around line 1034:
Expected text after =item, not a bullet
- Around line 1038:
Expected text after =item, not a bullet
- Around line 1062:
Expected text after =item, not a bullet
- Around line 1128:
Expected text after =item, not a bullet
- Around line 1132:
Expected text after =item, not a bullet
- Around line 1144:
Expected text after =item, not a bullet
- Around line 1190:
Expected text after =item, not a bullet
- Around line 1194:
Expected text after =item, not a bullet
- Around line 1214:
Expected text after =item, not a bullet
- Around line 1278:
Expected text after =item, not a bullet
- Around line 1282:
Expected text after =item, not a bullet
- Around line 1302:
Expected text after =item, not a bullet