## Subgraph Centrality

Subgraph Centrality

• Accounts for the participation of a node in all subgraphs of the network
• Smaller subgraphs are given more weight than larger ones, which makes this measure appropriate for characterizing network motifs (1)
• Measures density of eigenvalues within the network’s adjacency matrix A
• SC(i) = SUMt=0μt(i) / t! where μt(i) is the number of paths starting and ending with node i of length t and can be calculated by μt(i) = (Ak)ii
• This boils down to SC(i) = (eA)ii where eA is the matrix exponential of A

## Freeman’s Approach to Degree Centrality

Freeman’s Approach to Degree Centrality:

• Centrality is based on connections between nodes in the network
• Measure in-degree and the out-degree and degree percentage of entire network for each node
• Can measure network statistics such as mean, standard deviation, etc.
• Network Centralization calculation compares a network to the perfect star network of the same size
1. A star network of size N (nodes)
• Has one node whose in-degree is N-1 and whose out-degree is 0
• Other N-1 nodes have out-degree 1 and in-degree 0
2. Network Centralization = (N * D – m) / ((N-1)(N-2)) where N is the number of nodes, D is the max degree whether that is in or out, and m is the number of edges

References to use of this measure in literature:
1. Collaboration and Integration of Community-Based Health and Human Services in a Nonprofit Managed Care System
2. Interorganization Relationships Among HIV/AIDS Service Organizations in Baltimore: A Network Analysis
3. `Cheryl Alexander, Marina Piazza, Debra Mekos, Thomas Valente, Peers, schools, and adolescent cigarette smoking, Journal of Adolescent Health, Volume 29, Issue 1, July 2001, Pages 22-30, ISSN 1054-139X, DOI: 10.1016/S1054-139X(01)00210-5.`
(http://www.sciencedirect.com/science/article/B6T80-43B290W-4/2/8290dfdd3eb3d2e76e0fc7ec07681abd)

## Closeness Centrality

Closeness Centrality

• Nodes with short geodesic (shortest path between two nodes) distances to other nodes tend to have higher closeness
• A vertex’s closeness is defined as the inverse of the mean geodesic distance from vertex v to any other vertex in the graph
• Given the definition of Closeness, a large number of algorithms exist to compute it efficiently.
• Varying algorithms also rank closeness so no single algorithm works best.

References to use of this measure in literature:

## Bonacich’s Centrality

Bonacich’s Approach to Centrality (also known as Eigenvector Centrality)

• You are more central when there are more connections within your local network
• Fewer connections within your local network means you are more powerful
• Power comes from being connected to those that are powerless
• The Measure
• The centrality nodes in a network are given by: λ e = R e where R is matrix formulation of the network in question, e is an eigenvector of R, and λ is its associated eigenvalue
• Introduction of user-defined Β and α to measure centrality c such that c(α, Β) = α(I-ΒR)-1R*1 where c is a vector of node centralities, I is an identity matrix, and 1 is a column vector of 1’s.
• Β reflects the degree to which a node’s power is related to the power of the nodes it is connected to
• Intrepretation: A more positive Β means that other nodes centralities are taken more into account. A more negative Β means that a node’s power is reduced by the powerful nodes it is connected to.
• α simply scales node centrality

1. R documentation
2. Centrality and Centralization
3. Degree centrality:  Bonacich’s approach
4. Phillip Bonacich (1987) “Power and Centrality: A Family of Measures,” American Journal Of Sociology 92(5): 1170-1182.

References to use of this measure in literature:

## Betweenness Centrality

Betweenness Centrality

• The higher a node’s centrality is the more “dependent” other nodes are on it
• Based on shortest paths between nodes and the number of paths that pass through two points and the total number of paths
• BC(i) = SUMs≠i≠ t∈Vμst(i) / μst where μst is the number of paths from s and t and μst(i) is the number of paths from s and t that pass through node i

Algorithm

Input: V, a vertex and G, a graph

1. For all pairs of vertices (v1 and v2) in graph G, compute every shortest path between them
2. Using v1 and v2, compute the fraction of paths between these vertices that pass through V
3. Sum over all pairs of vertices