Graph Edge Sampling

Edge sampling is a technique to deal with weighted edges in large [[graph]] What is Graph 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 … . For weighted graph, one treatment is to create multiple edges between the same nodes but removing the weights. But this will require a lot of memory.

Edge sampling as a method samples edges with a probability proportional to the weights. By sampling and creating sampled binary edges, we create new unweighted graphs that represents the original graph.