For each metric, we list the most general type of compatible networks (see types of input networks for a further discussion). However, note that metrics for binary and undirected networks will be often faster to compute than their generalized counterparts.
All network metrics should be compared to metrics extracted from corresponding reference ( null model) networks.
Network types:
WD, weighted and directed,
WU, weighted and undirected,
BD, binary and directed,
BU, binary and undirected.
Density, Degree, Assortativity
- density_und.m (BU, WU networks)
Density is the proportion of the number of present connections in the network, to the maximum possible number of connections. Connection weights are ignored.
See e.g. Sporns (2002). Contributor: OS.
- density_dir.m (BD, WD networks)
Density is the proportion of the number of present connections in the network, to the maximum possible number of connections. Connection weights are ignored.
See e.g. Sporns (2002). Contributor: OS.
- degrees_und.m (BU, WU networks)
In an undirected graph, the degree is the number of connections for individual nodes. Connection weights are ignored.
See Sporns (2002) for a discussion. Contributor: OS.
- strengths_dir.m (WD networks)
In a directed graph, instrength (outstrength) is the sum of incoming (outgoing) connection weights for
individual nodes. The strength is the sum of instrength and outstrength.
Reference: Barrat et al. (2004). Contributor: OS.
- jdegree.m (BD, WD networks)
Joint degree distribution. This function returns a matrix, in which the value of each element (u,v) corresponds to the number of nodes that have u outgoing connections and v incoming connections. Connection weights are ignored.
See Sporns (2002) for a discussion. Contributor: OS.
- matching_ind.m (BD, BU networks)
Matching index. For any two nodes u and v, the matching index computes the amount of overlap in the connection patterns of u and v. Self-connections and cross-connections between u and v are ignored. For undirected networks, all outputs of this function are identical. The matching index is a symmetric quantity, similar to a correlation or a dot product, the function returns only the upper triangle of the matching matrix.
Reference: Hilgetag et al. (2002). Contributor: OS.
- assortativity.m (BD, BU, WD, WU networks)
Assortativity coefficient. Essentially, the assortativity a correlation coefficient for the degrees of linked nodes. A positive assortativity coefficient indicates that nodes tend to link to other nodes with the same or similar degree. The function accepts weighted networks, but the connection weights are ignored.
After Newman (2003). Contributor: OS.
Clustering
- clustering_coef_bu.m (BU networks)
Clustering coefficient. For an individual node, the clustering coefficient is defined as the fraction of the existing number, to the total possible number of neighbor-neighbor links.
Reference: Watts and Strogatz (1998). Contributor: MR.
.
-
A metric similar to the clustering coefficient, based upon the calculation of the harmonic mean of neighbor-neighbor distances. For directed networks, this function works on the out-degree.
Reference: Latora and Marchiori (2001). Contributor: MR.
.
- clustering_coef_bd.m (BD networks)
Clustering coefficient, generalized to directed networks, using the approach of Fagiolo.
Reference: Fagiolo (2007). Contributor: MR.
.
- clustering_coef_wu.m (WU networks)
Clustering coefficient, generalized to weighted networks, using the approach of Onnela et al.
Reference: Onnela et al. (2005). Contributor: MR.
.
- clustering_coef_wd.m (WD networks)
Clustering coefficient, generalized to weighted and directed networks, using the combined approaches of Fagiolo and Onnela et al.
References: Fagiolo (2007), Onnela et al. (2005). Contributor: MR.
.
Note that the generalized versions of the clustering coefficient are generally slower to compute.
Paths, Distances and Cycles
- findpaths.m (BD networks)
Paths are sequences of linked nodes, that never visit a single node more than once. This function finds all paths that start at a set of source vertices, up to a specified length. Warning: very memory-intensive.
See e.g. Sporns (2002). Contributor: OS.
.
- findwalks.m (BD networks)
Walks are sequences of linked nodes, that may visit a single node more than once. This function finds the number of walks of a given length, between any two nodes.
See e.g. Sporns (2002). Contributor: OS.
.
- reachdist.m (BD networks)
Reachability and distance matrices. For any two nodes u and v, the reachability matrix element (u,v) takes the value of 1 if u and v are connected by a path, and 0 if u and v are disconnected. The distance matrix element (u,v) denotes the length of the shortest path between u and v. Note that this function returns nonzero entries on the main diagonal of the distance matrix, corresponding to the length of the shortest cycles (see below).
See e.g. Sporns (2002). Contributor: OS.
.
- breadthdist.m (BD networks)
An alternative function for the reachability and distance matrices (using the breadth first search algorithm). This function may use less memory than reachdist.m, but reachdist.m is faster most of the time. This function requires an auxiliary function breadth.m. Contributor: OS.
.
- distance_bin.m (BD networks)
Another function for the distance matrix. If any two nodes u and v are disconnected, the value of the entry (u,v) is set to infinity. The value of self-self distances (u,u) is set to 0. Consequently, two nodes are connected if they have a finite non-zero distance.
Contributor: MR.
.
-
A global efficiency matrix is the inverse of the distance matrix (with self-self distances set to 0). Calculating the global efficiency is advantageous over distance in disconnected networks: the efficiency between disconnected pairs of nodes is set to 0 (the inverse of infinity), hence enabling the calculation of network wide averages (which become meaningless on distance matrices).
Reference: Latora and Marchiori (2001). Contributor: MR.
.
- distance_wei.m (WD networks)
Distance matrix for weighted networks. The input matrix must be a mapping from weight to distance. For instance, in a weighted correlation network, higher correlations are more naturally interpreted as shorter distances. Consequently, in this case, the input matrix should be some inverse of the connectivity matrix.
Algorithm: Dijkstra's algorithm. Contributor: MR.
.
- charpath.m (WD networks)
This function outputs four distance based metrics. Characteristic path length is the average shortest path length. Node eccentricity is the maximal shortest path length between a node and any other node. Network radius is the minimum eccentricity, while network diameter is the maximum eccentricity.
See Sporns (2002) for a discussion. Contributor: OS.
.
- cycprob.m (BD networks)
Cycle probability. Cycles are paths which begin and end at the same node. Cycle probability for path length d, is the fraction of all paths of length d-1 that may be extended to form cycles of length d.
See Sporns (2002) for a discussion. Contributor: OS.
Centrality
Centrality metrics attempt to describe nodes or links which play an important part in the network. Some centrality metrics have already been described in previous sections: for instance degree functions allow to determine nodes with a large number of connections ("degree centrality"), while distance functions allow to determine nodes which are closest on average to all other nodes ("closeness centrality").
- betweenness_bin.m (BD networks)
Nodal betweenness centrality: the fraction of all shortest paths in the network that traverse a given node. Hence nodes with high values of betweenness centrality participate in a large number of shortest paths.
Algorithm: A fast algebraic algorithm of Kintali (2008), generalized to directed/disconnected networks. Contributor: MR.
.
- edge_betweenness_bin.m (BD networks)
Edge betweenness centrality: the fraction of all shortest paths in the network that traverse a given edge (link). This function outputs an edge betweenness matrix. Note that zero entries may correspond to an absence of an edge, or to an edge with betweenness of 0 -- a comparison with the connectivity matrix will clear up potential confusion. This function may also return nodal betweenness centrality.
Algorithm: Brandes (2001). Contributor: MR.
.
- betweenness_wei.m (WD networks)
Nodal betweenness centrality for weighted networks. The input matrix must be a mapping from weight to distance (see description for distance_wei.m). Algorithm: Brandes (2001). Contributor: MR.
.
- edge_betweenness_wei.m (WD networks)
Edge betweenness centrality for weighted networks. This function may also return nodal betweenness centrality. The input matrix must be a mapping from weight to distance (see description for distance_wei.m). Algorithm: Brandes (2001). Contributor: MR.
.
-
erange.m (BD networks)
Shorcuts are links which significantly reduce the characteristic path length. This function detects shortcuts, hence being a variant of edge betweenness centrality.
Reference: Watts (1999). Contributor: OS.
top
Motifs
Motifs were introduced by Milo et al. (2002), as small network "building blocks" (subnetworks). Sporns and Kotter (2004) have extended the idea to differentiate between structural motifs (the common notion of a motif), and functional motifs (all motifs occuring "within" a structural motif). Onnela et al. (2005) generalized the notion of a motif to weighted networks. Motif counts should be compared to a randomized network, for a meaningful interpretation (see Reference Networks).
- motif3struct_bin.m; motif4struct_bin.m (BD networks)
Structural motif counts (classes 3 and 4) for binary networks -- following the original definition of a motif. Motif 3 legend is here. Reference: Milo et al. (2002). Contributor: MR.
.
- motif3funct_bin.m; motif4funct_bin.m (BD networks)
Functional motif counts (classes 3 and 4) for binary networks. Motif 3 legend is here. Reference: Sporns and Kotter (2004). Contributor: MR.
.
- motif3struct_wei.m; motif4struct_wei.m (WD networks)
Structural motif counts (classes 3 and 4) for weighted networks.
References: Milo et al. (2002), Onnela et al. (2005). Contributor: MR.
.
- motif3funct_wei.m; motif4funct_wei.m (WD networks)
Functional motif counts (classes 3 and 4) for weighted networks.
References: Sporns and Kotter (2004), Onnela et al. (2005). Contributor: MR.
.
- motif34lib.mat; make_motif34lib.m (library file, and generating function)
Motif library file (classes 3 and 4), required for all motif computations above.
The library file is generated by make_motif34lib.m.
Contributor: MR.
.
- find_motif34.m (BD networks)
This function provides the subnetwork patterns corresponding to the motif numbering scheme of the above functions, and vice versa.
Contributor: MR.
Modularity and Community Structure
- modularity_und.m (WU networks)
Network communities are groups of nodes that are highly connected to other nodes within their group, and less well connected to nodes outside their group. Maximized modularity is a value which measures how well a network may be delineated into distinct communities. This function outputs the optimized community structure, as well as the value of the maximized modularity for undirected networks.
Algorithm: Spectral algorithm of Newman (2006a,b). Contributor: MR.
.
- modularity_dir.m (WD networks)
Optimized community structure, and maximized modularity for directed networks.
Algorithm: Generalization of the algorithm of Newman (2006) to directed networks: Leicht and Newman (2007). Contributor: MR.
.
- module_degree_zscore.m; participation_coef.m (BD networks)
Degree based metrics for classifying nodes in the context of community structure. The z-score describes how well the nodes are connected to other nodes within their modules. Participation coefficient describes how well the nodal connections are distributed across different modules. Note that, for directed networks, these functions compute the metrics based on the out-degree.
Reference: Guimera and Amaral (2005). Contributor: MR.
|
|