Statistics of Graphs

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.

Graph Clustering Coefficient
Local 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$. Closed Triangles Ego Graph Counting the closed triangles of the ego graph of a node and normalize it by the total possible number of triangles is also a measure of clustering coefficients. If …

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

This iteration can be used to test if two graphs are isomorphism.

Neighborhood Overlap

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

Planted: by ;

No backlinks identified. Reference this note using the Note ID wiki/graph/basics/ in other notes to connect them.
Links to:

L Ma (2021). 'Statistics of Graphs', Datumorphism, 09 April. Available at: