Graph Basics

Some basic concepts about graph

4 Solving Problems on Graph

Published:
Category: { Graph }
Summary: Graphs can be used in many problem and there are many possible problems on graphs. We will mention a few popular problems on graphs12. Node Classification Is the user in black a bot or a normal user?Created based on the text in Hamilton2020 Given graph that has incomplete attribute labeling of the nodes, predict the attributes on the nodes. The following concepts can be used to classify nodes. [[Homophily]] Homophily on Graph 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.
Pages: 4

3 Graphs Spectral Methods

Published:
Category: { Graph }
Summary: The [[Ratio Cut]] Graph Cuts Cut For a subset of nodes $\mathcal A\subset \mathcal V$, the rest of nodes can be denoted as $\bar {\mathcal A} = \mathcal V \setminus \mathcal A$. In other words, $\mathcal A \cup \bar {\mathcal A} = \mathcal V$ and $\mathcal A \cap \bar {\mathcal A} = \emptyset$. That being said, the nodes can be partitioned into two subsets, $\mathcal A$ and $\bar {\mathcal A}$. The cut of this partition is defined as the total number of edges between them, $$ \operatorname{Cut} \left( \mathcal A, … is closely related to the [[Graph Laplacians]] Graph Laplacians Laplacian is a useful representation of graphs.
Pages: 4

2 Statistics of Graphs

Published:
Category: { Graph }
Summary: 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: Eigenvector Centrality of a Graph 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$.
Pages: 4

1 What is Graph

Published:
Category: { Graph }
Summary: Graph A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$, $$ \mathcal G = ( \mathcal V, \mathcal E). $$ Edges Edges are relations between nodes. For $u\in \mathcal V$ and $v\in \mathcal V$, if there is an edge between them, then $(u, v)\in \mathcal E$. Representations of Graph There are different representations of a graph. Adjacency Matrix A adjacency matrix of a graph represents the nodes using row and column indices and edges using elements of the matrix. For simple graph, the adjacency matrix is rank two and dimension $\lvert \mathcal V \rvert \times \lvert \mathcal V \rvert$.
Pages: 4