Graph measures
Graph measures (ROI-level)
All ROI-level graph measures below are based on user-defined nondirectional graphs with nodes = ROIs, and edges = supra-threshold connections. For each subject (and condition) a graph adjacency matrix A is computed by thresholding the associated ROI-to-ROI Correlation (RRC) matrix r by an absolute (e.g. z>0.5) or relative (e.g. highest 10%) threshold. Then, from the resulting graphs, a number of measures can be computed addressing topological properties of each ROI within the graph as well as of the entire network of ROIs (see Latora and Marchiori, 2001, and Achard and Bullmore, 2007, for further details about these and other graph theoretical measures)
Degree & Cost
Degree and Cost are defined, respectively, at each node as the number (degree) or proportion (cost) of edges from/to each node. Similarly, network degree/cost represent the average or the degree/cost across all nodes within a graph:
where A is an adjacency matrix, N is the total number of nodes in a graph, c is the cost of a graph (and of each individual node/ROI), and d is the degree of a graph (and of each individual node/ROI)
Degree and Cost at each node/ROI represent measures of network centrality, characterizing the degree of local connectedness of each ROI within a graph. Adjacency matrix thresholding is typically implemented using a fixed network cost level (e.g. keeping the strongest 10% of connections) in order to allow sensitive between-network comparisons of other graph measures of interest
Average path distance
Path distance between each pair of nodes in a graph is defined as the minimum number of edges traversed in an optimal path between them. Average path distance at each node is defined as the average path-distance between this node and all other nodes in the subgraph of connected nodes:
where D is the shortest-path distance matrix, N is the total number of nodes in a graph, and L is the averages path distance of a graph (and of each individual node/ROI)
Average path distance represents a measure of node centrality within a network, characterizing the degree of global connectedness of each ROI within a graph. Similarly, network average path distance represents a measure of inter-connectedness or radius of the entire network (e.g. random graphs have comparatively low/compact average path distances, compared to grids)
Clustering Coefficient
Clustering Coefficient is defined as the proportion of connected edges in the local neighboring sub-graph for each node/ROI:
where d is the degree of each node, A is the adjacency matrix within the neighboring sub-graph at each node, characterized by all nodes neighboring this node and all existing edges among them, and CC is the clustering coefficient of a graph (and of each individual node/ROI)
Clustering coefficient represents a measure of local integration, characterizing the degree of inter-connectedness among all nodes within a node neighboring sub-graph. Similarly, network clustering coefficient represents a measure of network locality or coherence (e.g. grid topologies have comparatively high clustering coefficients, compared to random graphs)
Global Efficiency
Global Efficiency at a node is defined as the average of inverse-distances between this node and all other nodes in the same graph:
where D is the shortest-path distance matrix, N is the number of nodes in a graph, and GE is the Global Efficiency of a graph (and of each individual node/ROI). Global efficiency at a node represents a measure of this node centrality within the network, characterizing the degree of global connectedness of each ROI. Similarly, network global efficiency represents a measure of inter-connectedness or radius of the entire network (e.g. with higher / more compact global efficiency in random graphs compared to grids)
Local Efficiency
Local Efficiency at each node is defined as the Global efficiency of the neighboring sub-graph of this node:
where d is the degree of each node, D is the shortest-path distance matrix within the neighboring sub-graph at each node, characterized by all nodes neighboring this node and all existing edges among them, and LE is the Local Efficiency of a graph (and of each individual node/ROI). Local efficiency represents a measure of local integration or coherence, characterizing the degree of inter-connectedness among all nodes within a node neighboring sub-graph. Similarly, network local efficiency represents a measure of local integration in a network (e.g. with higher local efficiency in grids compared to random graphs)
Betweenness Centrality
Betweenness centrality represents an alternative measure of node centrality within a graph. It is defined as the proportion of times that a node is part of a shortest-path between any two pairs of nodes within a graph.
where P is the set of nodes in shortest-path between each pair of nodes, N is the number of nodes in a graph, and BC is the Betweenness Centrality of a graph (and of each individual node/ROI)
References
Achard, S., Bullmore, E. (2007). Efficiency and cost of economical brain functional networks. PLoS Comput. Biol. 3, e17
Latora, V., Marchiori, M. (2001). Efficient behavior of small-world networks. Physical Review Letters 87: 198701-4