This is the user sandbox of Deriteidavid. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Graph Voronoi Diagrams

Graph Voronoi Diagrams are a generalization of Voronoi diagrams to graphs. Voronoi diagrams are a common way of partitioning metric spaces into regions or cells around a given set of points called seeds or generator points, such that each point of the space belongs to the cell of the closest seed. A similar partitioning can be applied on graphs if we set a few generator nodes, associate positive values to edges and define the distance between any pair of nodes as the shortest path connecting the two nodes. This generalization was first explored by Marin Erwig in ^[1].

Definition

Let $G=(V,E)$ be a directed and weighted graph with the set $V$ of $N$ vertices (nodes) and set $E$ of $M$ edges (links). We denote the length (weight) of an edge connecting nodes $\nu$ and $\mu$ as $l(\nu ,\mu )>0$ . The length of a path is obtained by summing up the length of edges constituting the path. The distance $d(\nu _{i},\nu _{j})$ between two nodes $\nu _{i}$ and $\nu _{j}$ is the length of the shortest path between the two nodes. Thus, the definition of an edge length assures that the graph can be treated as a metric space. The simplest choice of $l(\nu ,\mu )=1$ if $\nu$ and $\mu$ are directly connected, $0$ otherwise.

Let us now choose a set $S\equiv (\gamma _{1},\gamma _{2},...,\gamma _{g})\subset V$ of generator points or seeds. The Voronoi diagram of graph $G$ with respect to $S$ is thus the partitioning of $V$ into node sets $V_{1},V_{2},...,V_{g}\subset V$ , where each point set or Voronoi cell is associated with a generator point and

1. The Voronoi cells cover the original graph with no overlaps:

$\bigcup _{i=1}^{g}V_{i}=V$ and $V_{i}\bigcap V_{j}=\varnothing$ where $i,j=1,2,...,g.$

2. Nodes that belong to a Voronoi cell are closest to the generator point associated with the cell:

$d(\nu ,\gamma _{i})\leqslant d(\nu ,\gamma _{j}),$ for all $\nu \in V_{i}$ where $i,j=1,2,...,g$

Mathematical properties of graph Voronoi diagrams, along with different methods for their identification and their respective computational complexity, are detailed in ^[4]. This definition has been quoted from ^[3].

Applications

General

The author of the original paper introducing the concept suggested several applications of graph Voronoi diagrams. These include an alternative solution for the facility location problem, algorithms for collision-free moving and detection algorithms for special structural elements of graphs called anti-centers and furthest points ^[1].

Traffic and delivery optimization

A. Okabe and colleagues offered some new algorithms working with graph Voronoi diagrams, also exploring some applications in the traffic of Kyoto. They suggested that most of the time it is not optimal to model traffic within a Euclidean space, but as a weighted graph where intersections serve as nodes and streets connecting the intersections as weighted links. This way, for example delivery services can easily find the right courier, based on their Voronoi cells and the position of the order.^[5]

Community detection

In ^[3] it has been have shown that graph Voronoi diagrams can be used to detect communities. Generator points can be selected arbitrarily, especially if one knows at least one node from each community. Otherwise the method needs rules for: setting the length of edges and choosing the generator nodes. Then communities can be identified as the graph Voronoi cells. The authors of the paper propose one for each rule: the distance measure as the inverse of the edge clustering coefficient, which is large when the two nodes connected have many common neighbors. For detecting communities larger clustering coefficient will indicate smaller distance. In graphs each node is characterized by the link density of its neighborhood. For generator points nodes with the highest local density within a region of a given radius were selected. Varying this radius allows community detection at different scales. Overall, the algorithm has 3 main steps: assigning distances to edges; identifying generator nodes and constructing the Voronoi diagram. When applying the algorithm the best strategy is to gradually increase the radius. This method has shown high reliability compared with other popular community detection methods as well as on benchmark networks.

Computational efficiency

There are many algorithms suggested by papers studying graph Voronoi diagrams, but the theoretical complexity of partitioning a graph into Voronoi cells is $O(NlogN)$ , where $N$ is the number of vertices^[4]^[3].

References

^ ^a ^b Erwig M 2000 The graph Voronoi diagram with applications Networks 36 156–63
^ Bastian M, Heymann S and Jacomy M 2009 Gephi: an open source software for exploring and manipulating networks ICWSM: AAAI Int. Conf. on Weblogs and Social Media 361–2
^ ^a ^b ^c ^d ^e Dávid Deritei et al 2014 New J. Phys. 16 063007
^ ^a ^b Aurenhammer F 1991 Voronoi diagrams—a survey of a fundamental geometric data structure ACM Comput. Surv. 23 345–405
^ Okabe, Atsuyuki, et al. "Generalized network Voronoi diagrams: Concepts, computational methods, and applications." International Journal of Geographical Information Science 22.9 (2008): 965-994.

[Erwig-1] Erwig M 2000 The graph Voronoi diagram with applications Networks 36 156–63

[gephi-2] Bastian M, Heymann S and Jacomy M 2009 Gephi: an open source software for exploring and manipulating networks ICWSM: AAAI Int. Conf. on Weblogs and Social Media 361–2

[Deritei-3] Dávid Deritei et al 2014 New J. Phys. 16 063007

[Aurenhammer-4] Aurenhammer F 1991 Voronoi diagrams—a survey of a fundamental geometric data structure ACM Comput. Surv. 23 345–405

[5] Okabe, Atsuyuki, et al. "Generalized network Voronoi diagrams: Concepts, computational methods, and applications." International Journal of Geographical Information Science 22.9 (2008): 965-994.

[1]

[2]

[3]

[4]

[5]