Graph

Knowledge snippets about graph

Introduction: My Knowledge Cards

Weisfeiler-Lehman Kernel

Published:
Category: { Graph }
Summary: 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.
Pages: 20

Structural Equivalence on Graph

Published:
Category: { Graph }
Tags:
Summary: Structural Equivalence means that nodes with similar neighborhood structures will share similar attributes.
Pages: 20

Node Degree

Published:
Category: { Graph }
Summary: Node degree of a node $u$ $$ d_u = \sum_{v\in \mathcal V} A[u,v], $$ where $A$ is the adjacency matrix.
Pages: 20

Local Variant of Clustering Coefficient

Published:
Category: { Graph }
Summary: $$ 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.
Pages: 20

Homophily on Graph

Published:
Category: { Graph }
Summary: Homophily is the principle that a contact between similar people occurs at ahigher rate than among dissimilar people – McPherson20011 McPherson2001 McPherson M, Smith-Lovin L, Cook JM. Birds of a Feather: Homophily in Social Networks. Annu Rev Sociol. 2001;27: 415–444. doi:10.1146/annurev.soc.27.1.415  ↩︎
Pages: 20

Heterophily on Graph

Published:
Category: { Graph }
Summary: Heterophily is the tendency to differ from others. Heterophily on a graph is the tendency to connect to nodes that are different from itself, e.g., nodes with different attributes have higher probability of edge.
Pages: 20

Graph Laplacians

Published:
Category: { Graph }
Summary: Laplacian is a useful representation of graphs. The unnormalized Laplacian is $$ \mathbf L = \mathbf D - \mathbf A, $$ where $\mathbf A$ is the adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link and $\mathbf D$ is the degree matrix, i.
Pages: 20

Graph Cuts

Published:
Category: { Graph }
Summary: Cut For a subset of nodes $\mathcal A\subset \mathcal V$, with the rest of nodes $\bar {\mathcal A} = \mathcal V \setminus \mathcal A$. For $k$ such subsets of nodes, $\mathcal A_1, \cdots, $\mathcal A_k$, the cut is the total number of edges between $\mathcal A$ and $\bar{\mathcal A}$ 1, $$ \operatorname{Cut} \left( \mathcal A_1, \cdots, $\mathcal A_k \right) = \frac{1}{2} \sum_{k=1}^K \lvert (u, v)\in \mathcal E: u\in \mathcal A_k, v\in \bar{\mathcal A_k} \rvert. $$ For smaller cut value, the proposed patches $\mathcal A_1, \cdots, \mathcal A_k$ are more disconnected from the overall graph. This definition is biased towards smaller graphlets, i.
Pages: 20

Graph Adjacency Matrix

Published:
Category: { Graph }
Tags:
Summary: A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link
Pages: 20

Eigenvector Centrality of a Graph

Published:
Category: { Graph }
Summary: Given a graph with adjacency matrix $\mathbf A$, the eigenvector centrality is $$ \mathbf e_u = \frac{1}{\lambda} \sum_{v\in\mathcal V} \mathbf A[u,v] \mathbf e_v, \qquad \forall u \in \mathcal V. $$ Why is it called Eigenvector Centrality The definition is equivalent to $$ \lambda \mathbf e = \mathbf A\mathbf e. $$ Power Iteration The solution to $\mathbf e$ is the eigenvector that corresponds to the largest eigenvalue $\lambda_1$. Power iteration method can help us get this eigenvector, i.e., the $^{(t+1)}$ iteration is related to the previous iteration $^{(t)}$, through the following relation, $$ \mathbf e^{(t+1)} = \mathbf A \mathbf e^{(t)}.
Pages: 20

Betweenness Centrality of a Graph

Published:
Category: { Graph }
Summary: Betweenness centrality of a node $v$ is measurement of how likely the shortest path between two nodes $u_s$ and $u_t$ is gonna pass through node $v$, $$ c(v) = \sum_{v\neq u_s\neq u_t} \frac{\sigma_{u_su_t}(v) }{\sigma_{u_su_t}}, $$ where $\sigma_{u_su_t}(v)$ is the number of shortest path between $u_s$ and $u_t$, and passing through $u$, while $\sigma_{u_su_t}$ is the number of shortest path between $u_s$ and $u_t$. A figure from wikipedia demonstrates this idea well. The nodes on the outreach have smaller betweenness centrality, while the nodes in the core have higher betweenness centrality. Source: Wikipedia Outreach and Core It is almost like cheating using the work “outreach” and “core” here.
Pages: 20

Graph Local Overlap Measure: Sorensen Index

Published:
Category: { Graph }
Summary: The Sorensen index is $$ \mathbf S_{\text{Sorensen}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap \mathcal N(v) \rvert }{ d_u + d_v}, $$ where $d_u$ is the node degree of node $u$ and $\mathcal N(u)$ is the neighbor nodes of $u$.
Pages: 20

Graph Local Overlap Measure: Salton Index

Published:
Category: { Graph }
Summary: The Salton index is $$ \mathbf S_{\text{Salton}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap \mathcal N(v) \rvert }{ \sqrt{d_u d_v}}, $$ where $d_u$ is the node degree of node $u$ and $\mathcal N(u)$ is the neighbor nodes of $u$.
Pages: 20

Graph Local Overlap Measure: Resource Allocation Index

Published:
Category: { Graph }
Summary: The Resource Allocation (RA) index is $$ \mathbf S_{\text{RA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) \cap \mathcal N(v)} \frac{1}{d_u}, $$ where $d_u$ is the node degree of node $u$ and $\mathcal N(u)$ is the neighbor nodes of $u$.
Pages: 20

Graph Local Overlap Measure: Adamic Adar Index

Published:
Category: { Graph }
Summary: The Adamic Adar (AA) index is1 $$ \mathbf S_{\text{AA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) \cap \mathcal N(v)} \frac{1}{\log d_u}, $$ where $d_u$ is the node degree of node $u$ and $\mathcal N(u)$ is the neighbor nodes of $u$. If two nodes have shared neighbor, the degree of the neighbors will be at least 2. So it is safe to use $1/\log d_u$. Adamic2003 Adamic LA, Adar E. Friends and neighbors on the Web. Soc Networks. 2003;25: 211–230. doi:10.1016/S0378-8733(03)00009-1  ↩︎
Pages: 20

Graph Isomorphism

Published:
Category: { Graph }
Tags:
Summary: For two graphs, $\mathcal G$ and $\mathcal H$, the two graphs are isomorphism on the following condition $$ u, v \text{ adjacent in } G \iff u, v \text{ adjacent in } H. $$ An algorithm to find approximate isomorphism is the Weisfeiler Lehman Method 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.
Pages: 20

Graph Global Overlap Measure: Random Walk Similarity

Published:
Category: { Graph }
Summary: Random Walk Construct a stochastic transfer matrix $P$ by normalizing the adjacency matrix $\mathbf A$ using the node degrees of the target nodes, $$ \mathbf P = \mathbf A \mathbf D^{-1}, $$ where $\mathbf A$ is the adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link and $\mathbf D$ is a diagonalized matrix with the diagonal elements being the degrees.
Pages: 20

Graph Global Overlap Measure: Leicht-Holme-Newman Index

Published:
Category: { Graph }
Summary: From Katz Index to LHN Index Katz Index 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], $$ where $\mathbf A^i[u, v]$ is the matrix $\mathbf A$ to the $i$th power. Some for $\beta^i$. The Katz index describes the similarity between of node $u$ and node $v$. Do not confuse power with contravariant indices For readers familiar with tensor notations, it might be confusing. We some times use contravariant indices on the top right of the tensor notation. But here ${}^{i}$ means to the $i$th … has a knob to tune the punishment towards longer paths.
Pages: 20

Graph Global Overlap Measure: Katz Index

Published:
Category: { Graph }
Summary: The Katz index is $$ \mathbf S_{\text{Katz}}[u,v] = \sum_{i=1}^\infty \beta^i \mathbf A^i[u, v], $$ where $\mathbf A^i[u, v]$ is the matrix $\mathbf A$ to the $i$th power. Some for $\beta^i$. The Katz index describes the similarity between of node $u$ and node $v$. Do not confuse power with contravariant indices For readers familiar with tensor notations, it might be confusing. We some times use contravariant indices on the top right of the tensor notation. But here ${}^{i}$ means to the $i$th power. The index is proved to be the following $$ \mathbf S_{\text{Katz}} = (\mathbf I - \beta \mathbf A)^{-1} - \mathbf I.
Pages: 20

Graph Convolution Operator

Published:
Category: { Graph }
Summary: For a given graph $\mathcal G$, we have an attribute on each node, denoted as $f_v$. All the node attributes put together can be written as a list $\mathbf f\to (f_{v_1}, f_{v_2}, \cdots, f_{v_N})$. Convolution on graph is combining attributes on nodes with their neighbors'. The adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$ for the graph Public Domain, Link $\mathbf A$ applied on all node attributes $\mathbf f$ is such an operation, i.
Pages: 20