Statistics of Graphs

#Graph #Basics #Statistics

Local Statistics

Node Degree

Node Degree
Node degree of a node $u$ $$ d_u = \sum_{v\in \mathcal V} A[u,v], $$ where $A$ is the adjacency matrix.

Node Centrality

Importance of a node on a graph:

Clustering Coefficients

Proportion of motifs, e.g., closed triangles, in a node’s neighborhood.

Local Variant of Clustering Coefficient
$$ c_u = \frac{ \lvert (v_1,v_2)\in \mathcal E: v_1, v_2 \in \mathcal N(u) \rvert}{ \color{red}{d_n \choose 2} }, $$ where $\color{red}{d_n \choose 2}$ means all the possible combinations of neighbor nodes, and $\mathcal N(u)$ is the set of nodes that are neighbor to $u$. Ego Graph If $c_u=1$, the ego graph of $u$ is fully connected; If $c_u=0$, the ego graph of $u$ is a star.

Graph Level Statistics

Bag of Nodes

Using the statistics of the local statistics, e.g., distribution of node degrees, as graph level statistics.

Weisfeiler-Lehmen Kernel

Weisfeiler-Lehman Kernel
The Weisfeiler-Lehman kernel is an iterative integration of neighborhood information. We initialize the labels for each node using its own node degree. At each step, we take the neighboring node degrees to form a multiset. At step $K$, we have the multisets for each node. Those multisets at each node can be processed to form an representation of the graph which is in turn used to calculate statistics of the graph. Iterate $k$ steps This iteration can be used to test if two graphs are isomorphism1. Shervashidze2011 Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM.

Neighborhood Overlap

We can define many different similarity measures $\mathbf S$.

Published: by ;

L Ma (2021). 'Statistics of Graphs', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/statistics-of-graphs/.

Current Ref:

  • wiki/graph/basics/statistics-of-graphs.md

Links to:

What is Graph

Graph A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$, $$ \mathcal G = ( \mathcal …

Node Degree

Node degree of a node $u$ $$ d_u = \sum_{v\in \mathcal V} A[u,v], $$ where $A$ is the adjacency …

Eigenvector Centrality of a Graph

Given a graph with adjacency matrix $\mathbf A$, the eigenvector centrality is $$ \mathbf e_u = …

Betweenness Centrality of a Graph

Betweenness centrality of a node $v$ is measurement of how likely the shortest path between two …

Local Variant of Clustering Coefficient

$$ c_u = \frac{ \lvert (v_1,v_2)\in \mathcal E: v_1, v_2 \in \mathcal N(u) \rvert}{ \color{red}{d_n …

Graph Local Overlap Measure: Sorensen Index

The Sorensen index is $$ \mathbf S_{\text{Sorensen}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap …

Graph Local Overlap Measure: Salton Index

The Salton index is $$ \mathbf S_{\text{Salton}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap \mathcal …

Jaccard Similarity

Jaccard index is the ratio of the size of the intersect of the set and the size of the union of the …

Graph Local Overlap Measure: Resource Allocation Index

The Resource Allocation (RA) index is $$ \mathbf S_{\text{RA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) …

Graph Local Overlap Measure: Adamic Adar Index

The Adamic Adar (AA) index is1 $$ \mathbf S_{\text{AA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) \cap …

Graph Global Overlap Measure: Katz Index

The Katz index is $$ \mathbf S_{\text{Katz}}[u,v] = \sum_{i=1}^\infty \beta^i \mathbf A^i[u, v], $$ …

Graph Global Overlap Measure: Leicht-Holme-Newman Index

From Katz Index to LHN Index Katz Index Graph Global Overlap Measure: Katz Index The Katz index is …

Graph Global Overlap Measure: Random Walk Similarity

Random Walk Construct a stochastic transfer matrix $P$ by normalizing the adjacency matrix $\mathbf …