# Weisfeiler-Lehman Kernel

Published:
Category: { Graph }
Tags:
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]] Multiset, mset or bag A bag is a set in which duplicate elements are allowed. An ordered bag is a list that we use in programming. . 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: 22

# Structural Equivalence on Graph

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

# Node Degree

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

# Homophily on Graph

Published:
Category: { Graph }
Tags:
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: 22

# Heterophily on Graph

Published:
Category: { Graph }
Tags:
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: 22

# Graph Laplacians

Published:
Category: { Graph }
Tags:
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: 22

# Graph Cuts

Published:
Category: { Graph }
Tags:
Pages: 22

# Betweenness Centrality of a Graph

Published:
Category: { Graph }
Tags:
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: 22

# Graph Local Overlap Measure: Sorensen Index

Published:
Category: { Graph }
Tags:
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: 22

# Graph Local Overlap Measure: Salton Index

Published:
Category: { Graph }
Tags:
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: 22

# Graph Local Overlap Measure: Resource Allocation Index

Published:
Category: { Graph }
Tags:
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: 22

Published:
Category: { Graph }
Tags:
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: 22

# 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]] Multiset, mset or bag A bag is a set in which duplicate elements are allowed. An ordered bag is a list that we use in programming.
Pages: 22

# Graph Global Overlap Measure: Random Walk Similarity

Published:
Category: { Graph }
Tags:
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: 22

# Graph Global Overlap Measure: Leicht-Holme-Newman Index

Published:
Category: { Graph }
Tags:
Summary: The LHN index is a normalized similarity index. 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: 22

# Graph Global Overlap Measure: Katz Index

Published:
Category: { Graph }
Tags:
Pages: 22