List of measures

For each measure, we provide a brief description and include the type of compatible associated networks (see Network construction for more information).

More detailed information about each measure (including relevant journal references) is included inside individual function headers. Individual function headers may be accessed by typing  doc function_name  in the MATLAB command window.

Notes: 1. Measures for binary and undirected networks will often be faster to compute than measures for weighted and directed networks. 2. Most network measures should be compared with measures computed on corresponding reference (null model) networks.

Degree and Similarity

• Degree: Node degree is the number of links connected to the node. In directed networks, the in-degree is the number of inward links and the out-degree is the number of outward links. Connection weights are ignored in calculations.

  • degrees_und.m (BU, WU networks); degrees_dir.m (BD, WD networks).

  • Contributor: OS.

• Strength: Node strength is the sum of weights of links connected to the node. In directed networks, the in-strength is the sum of inward link weights and the out-strength is the sum of outward link weights.

  • strengths_und.m (WU networks); strengths_dir.m (WD networks).

  • strengths_und_sign.m (WU signed networks).

  • Contributor: OS, MR.

• Joint degree: 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.

  • jdegree.m (BD, WD networks).

  • Contributor: OS.

• Topological overlap: The m-th step generalized topological overlap measure quantifies the extent to which a pair of nodes have similar m-th step neighbors (nodes that are reachable by a path of at most length m).

  • gtom.m (BU networks).

  • Contributor: JG.

• Neighborhood overlap: These functions compute the overlap between the neighborhoods of pairs of nodes linked by edges.

  • edge_nei_overlap_bu.m (BU networks); edge_nei_overlap_bd.m (BD networks).

  • Contributor: OS.

• Matching index: The matching index computes for any two nodes u and v, the amount of overlap in the connection patterns of u and v. Self-connections and u-v connections are ignored. The matching index is a symmetric quantity, similar to a correlation or a dot product.

  • matching_ind_und.m (BU networks); matching_ind.m (BD networks).

  • Contributor: OS, RB.

top

Density and Rentian Scaling

• Density: Density is the fraction of present connections to possible connections. Connection weights are ignored in calculations.

  • density_und.m (BU, WU networks); density_dir.m (BD, WD networks).

  • Contributor: OS.

• Rentian scaling: Physical Rentian scaling is a property of systems that are cost-efficiently embedded into physical space. It is what is called a "topo-physical" property because it combines information regarding the topological organization of the network with information about the physical placement of connections.

  • rentian_scaling_2d.m; rentian_scaling_3d.m (BU networks).

  • Contributor: DB.

top

Clustering and Community Structure

• Clustering coefficient: The clustering coefficient is the fraction of triangles around a node and is equivalent to the fraction of node’s neighbors that are neighbors of each other.

  • clustering_coef_bu.m (BU networks); clustering_coef_bd.m (BD networks);

  • clustering_coef_wu.m (WU networks); clustering_coef_wd.m (WD networks);

  • clustering_coef_wu_sign.m (WU signed networks).

  • Note: The function clustering_coef_wu_sign.m includes several generalizations of the clustering coefficient. In contrast, the functions clustering_coef_wu.m and clustering_coef_wd.m contain only one generalization of the clustering coefficient.

  • Contributor: MR, JS.

• Transitivity: The transitivity is the ratio of triangles to triplets in the network and is an alternative to the clustering coefficient.

  • transitivity_bu.m (BU networks); transitivity_bd.m (BD networks);

  • transitivity_wu.m (WU networks); transitivity_wd.m (WD networks).

  • Contributors: AG, MR.

• Local efficiency: The local efficiency is the global efficiency (see below) computed on node neighborhoods, and is related to the clustering coefficient.

  • efficiency_bin.m (BU, BD networks); efficiency_wei.m (WU, WD networks).

  • Contributor: MR.

• Connected components: Connected components are subnetworks in which all pairs of nodes are connected by paths.

  • get_components.m (BU networks).

  • Contributor: JG.

• Community structure and modularity: The optimal community structure is a subdivision of the network into nonoverlapping groups of nodes in a way that maximizes the number of within-group edges, and minimizes the number of between-group edges. The modularity is a statistic that quantifies the degree to which the network may be subdivided into such clearly delineated groups.

  • community_louvain.m (BU, WU, BD, WD, signed networks): Louvain community detection algorithm with added finetuning.

  • modularity_und.m (BU, WU networks); modularity_dir.m (BD, WD networks): Newman's spectral community detection.

  • link_communities.m (BU, WU, BD, WD networks): Link-based community-detection algorithm (detects overlapping communities).

  • clique_communities.m (BU networks): Clique-percolation community-detection algorithm (detects overlapping communities).

  • Contributors: MR, JP, AG, DB.

  • Note: For similarity of community partitions see Network Comparison.

• Modularity degeneracy and consensus partitioning: Modularity degeneracy is the existence of multiple distinct high-modularity partitions of the same network. Consensus partitioning aims to provide a single consensus partition of these degenerate partitions.

  • agreement.m, agreement_weighted.m (BU, BD, WU, WD networks).

  • consensus_und.m (BU, BD, WU, WD networks).

  • Note: the inputs to these functions are not networks but some partitions of these networks (or derivatives of these partitions).

  • Contributor: RB.

top

Assortativity and Core Structure

• Assortativity: The assortativity coefficient is a correlation coefficient between the degrees of all nodes on two opposite ends of a link. A positive assortativity coefficient indicates that nodes tend to link to other nodes with the same or similar degree.

  • assortativity_bin.m (BU, BD networks).

  • assortativity_wei.m (WU, WD networks).

  • local_assortativity_wu_sign.m (WU signed networks).

  • Contributors: OS, JS, VT, MS, MR.

• Rich club coefficient: The rich club coefficient at level k is the fraction of edges that connect nodes of degree k or higher out of the maximum number of edges that such nodes might share.

  • rich_club_bu.m (BU networks); rich_club_bd.m (BD networks).

  • rich_club_wu.m (WU networks); rich_club_wd.m (WD networks).

  • Contributors: MH, OS.

• Core/periphery structure: The core/periphery subdivision is a partition of the network into two non-overlapping groups of nodes, a core group and a periphery group, in a way that maximizes the number/weight of within core-group edges, and minimizes the number/weight of within periphery-group edges.

  • core_periphery_dir.m (BU, BD, WU, WD networks).

  • Contributor: MR.

• K-core: The k-core is the largest subnetwork comprising nodes of degree at least k. The k-core is computed by recursively peeling off nodes with degree lower than k, until no such nodes remain in the subnetwork.

  • kcore_bu.m (BU networks); kcore_bd.m (BD networks).

  • Contributor: OS.

• S-core: The s-core is the largest subnetwork comprising nodes of strength at least s. The s-core is computed analogously to the more widely used k-core, but is based on node strengths instead of node degrees.

  • score_wu.m (WU networks).

  • Contributor: OS.

top

Paths and Distances

• Paths and walks: Paths are sequences of linked nodes that never visit a single node more than once. Walks are sequences of linked nodes that may visit a single node more than once.

  • findpaths.m (BU, BD networks); findwalks.m (BU, BD networks).

  • Contributor: OS.

• Distance and characteristic path length: The reachability matrix describes whether pairs of nodes are connected by paths (reachable). The distance matrix contains lengths of shortest paths between all pairs of nodes. The characteristic path length is the average shortest path length in the network.

  • distance_bin.m (BU, BD networks): distance matrix (algebraic algorithm).

  • reachdist.m (BU, BD networks): reachability and distance matrices (alternative algebraic algorithm -- returns nonzeros on the main diagonal, unlike distance_bin).

  • breadthdist.m (BU, BD networks): reachability and distance matrices (breadth-first search). This algorithm is slower but less memory-intensive compared to the above. This function requires an auxiliary function breadth.m.

  • retrieve_shortest_path.m (BU, BD, WU, WD networks): sequence of nodes that comprise the shortest path between a given source and target node.

  • distance_wei.m (WU, WD networks): distance matrix (Dijkstra's algorithm). The input matrix must be a mapping from weight to distance (usually weight inversion).

  • distance_wei_floyd.m (BU, BD, WU, WD networks): distance matrix (Floyd-Warshall algorithm). The input matrix may be a mapping from weight to distance (usually weight inversion), or may be the native weights matrix (in which case a weight transform to distance must be specified as the input).

  • Contributors: OS, MR, AA, RB.

• Characteristic path length, global efficiency, eccentricity, radius, diameter: The characteristic path length is the average shortest path length in the network. The global efficiency is the average inverse shortest path length in the network. The node eccentricity is the maximal shortest path length between a node and any other node. The radius is the minimum eccentricity and the diameter is the maximum eccentricity.

  • • charpath.m (BU, BD, WU, WD networks).

    • Contributor: OS.

• 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.

  • • cycprob.m (BU, BD networks)

    • Contributor: OS.

top

Efficiency and Diffusion

• Global and local efficiency: The global efficiency is the average inverse shortest path length in the network, and is inversely related to the characteristic path length. The local efficiency is the global efficiency computed on the neighborhood of the node, and is related to the clustering coefficient.

  • efficiency_bin.m (BU, BD networks); efficiency_wei.m (WU, WD networks); rout_efficiency.m (BU, BD, WU, WD networks).

  • Contributor: MR, AA.

• Mean first passage time: The first passage time is the expected number of steps it takes a random walker to reach one node from another.

  • mean_first_passage_time.m (BU, BD, WU, WD networks).

  • Contributor: JG.

• Diffusion efficiency: The diffusion efficiency is the inverse of the mean first passage time.

  • diffusion_efficiency.m (BU, BD, WU, WD networks).

  • Contributor: JG, AA.

• Resource efficiency: The resource efficiency is inversely proportional to the amount of resources, i.e. number of particles or messages, required to ensure that at least one of the messages will arrive from the source to the target node in exactly SPL steps, where SPL is the length of the shortest-path between source and target.

  • resource_efficiency_bin.m (BU networks).

  • Contributor: JG, AA.

• Path transitivity: Path transitivity is the density of local detours (triangles) that are available along the shortest-paths between all pairs of nodes.

  • path_transitivity.m (BU networks)

  • Contributor: JG.

• Search information: Search information is the amount of information (in bits) that a random walker needs to follow the shortest path between a given pair of nodes.

  • search_information.m (BU networks)

  • Contributor: AA, JG.

• Navigation: Navigation is a decentralized greedy strategy driven by communication between geometrically closest target nodes.

  • navigation_wu.m (WU networks)

  • Contributor: CS.

top

Centrality

Some centrality are listed in previous sections: degree functions allow to determine nodes with a large number of connections ("degree centrality"), while distance functions allow to determine nodes which are close to other nodes ("closeness centrality").

• Betweenness centrality: Node betweenness centrality is the fraction of all shortest paths in the network that contain a given node. Nodes with high values of betweenness centrality participate in a large number of shortest paths.

  • betweenness_bin.m (BU, BD networks): Kintali's algorithm.

  • betweenness_wei.m (WU, WD networks): Brandes's algorithm.

  • Contributor: MR.

• Edge betweenness centrality: Edge betweenness centrality is the fraction of all shortest paths in the network that contain a given edge. Edges with high values of betweenness centrality participate in a large number of shortest paths.

  • edge_betweenness_bin.m (BU, BD networks);

  • edge_betweenness_wei.m (WU, WD networks).

  • Contributor: MR.

• Within-module degree z-score: The within-module degree z-score is a within-module version of degree centrality. This measure requires a previously determined community structure (see above).

  • module_degree_zscore.m; (BU, BD, WU, WD networks).

  • Contributor: MR.

• Participation and related coefficients: Participation coefficient is a measure of diversity of intermodular connections of individual nodes. The gateway coefficient is a variant of the participation coefficient, weighted by the importance of individual connections. The diversity coefficient is a related measure, based on the Shannon entropy. All measures requires a previously determined community structure as input (see above).

  • participation_coef.m (BU, BD, WU, WD networks).

  • participation_coef_sign.m (WU signed networks).

  • gateway_coef_sign.m (WU signed networks).

  • diversity_coef_sign.m (WU signed networks).

  • Contributor: MR, JS.

• Eigenvector centrality: Eigenector centrality is a self-referential measure of centrality -- nodes have high eigenvector centrality if they connect to other nodes that have high eigenvector centrality.

  • eigenvector_centrality_und.m (BU, WU networks).

  • Contributors: XZ, RB.

• PageRank centrality: The PageRank centrality is a variant of eigenvector centrality.

  • pagerank_centrality.m (BU, WU networks).

  • Contributors: XZ, RB.

• Subgraph centrality: The subgraph centrality of a node is a weighted sum of closed walks of different lengths in the network starting and ending at the node.

  • subgraph_centrality.m (BU networks).

  • Contributors: XZ, RB.

• K-coreness centrality: The k-core is the largest subgraph comprising nodes of degree at least k. The coreness of a node is k if the node belongs to the k-core but not to the (k+1)-core.

  • kcoreness_centrality_bu.m (BU networks);

  • kcoreness_centrality_bd.m (BD networks).

  • Contributor: OS.

• Flow coefficient: The flow coefficient is similar to betweenness centrality, but computes centrality based on on local neighborhoods. The flow coefficient is inversely related to the clustering coefficient.

  • flow_coef_bd.m (BU, BD networks).

  • Contributor: OS.

• Shortcuts: Shorcuts are central edges which significantly reduce the characteristic path length in the network.

  • erange.m (BD networks).

  • Contributor: OS.

top

Motifs and self-similarity

• Structural motifs: Structural motifs (or simply motifs) are small (e.g. 3 or 4 node) patterns of local connectivity that occur in the network with a statistically surprising frequency. In weighted networks, the motif frequency may be supplemented by its weighted generalizations, the motif intensity and the motif coherence.

  • motif3struct_bin.m; motif4struct_bin.m (BD networks).

  • motif3struct_wei.m; motif4struct_wei.m (WD networks).

  • All functions require the library motif34lib.mat generated with make_motif34lib.m.

  • Motif legend: find_motif34.m (BD networks). This function returns all motif isomorphs for a given motif id and size. The function may also return the motif id for a given motif connection matrix. In addition, motif-3 legend is in Figure 1 of Sporns and Kötter (2004).

  • Contributor: MR.

• Functional motifs: Functional motifs are subsets of connection patterns embedded within structural motifs. Functional motif frequency is the frequency of functional motif occurence around a node. In weighted networks, the motif frequency may be supplemented by its weighted generalizations, the motif intensity and the motif coherence.

  • motif3funct_bin.m; motif4funct_bin.m (BD networks).

  • motif3funct_wei.m; motif4funct_wei.m (WD networks).

  • All functions require the library motif34lib.mat generated with make_motif34lib.m.

  • Motif legend: find_motif34.m (BD networks). This function returns all motif isomorphs for a given motif id and size. The function may also return the motif id for a given motif connection matrix. In addition, motif-3 legend is in Figure 1 of Sporns and Kötter (2004).

  • Contributor: MR.

• Quasi-idempotence: Quasi-idempotence is a measure of a correlation between a matrix and the corresponding matrix squared once, infinitely many times or anything in between. It thus quantifies how close the initial matrix is to being idempotent. High values represent a weighted graph wherein edge strengths are primarily determined by nodal strengths, or equivalently wherein the strength of each edge is closely related to the sum of all corresponding triangles spanning the rest of the network.

  • quasi_idempotence.m (WU networks).

  • Contributor: LM.

top