## 2 Preliminaries  
We consider graphs \(G(V,E)\), where \(V\) is the set of \(|V|=n\) vertices (nodes) and \(E\subseteq V\times V\) is the set of \(|E|=m\) edges (also called arcs or links). The distance \(d(v,w)\) between two nodes \(v,w\in V\) is defined as the length of a shortest path from \(v\) to \(w\), _i.e._, the minimum number of edges that have to be traversed to get from \(v\) to \(w\). We assume that our graphs are _undirected_, meaning that \((v,w)\in E\) iff \((w,v)\in E\) and thus \(d(v,w)=d(w,v)\) for all \(v,w\in V\). Note that each edge \((v,w)\) is thus included twice in \(E\): once as a link from \(v\) to \(w\) and once as a link from \(w\) to \(v\). We will also assume that \(G\) is connected, meaning that \(d(v,w)\) is always finite. Furthermore it is assumed that there are no parallel edges and no loops linking a node to itself. The neighborhood \(N(v)\) of a node \(v\) is defined as the set of all nodes connected to \(v\) via an edge: \(N(v)=\{w\in V\mid(v,w)\in E\}\). The degree \(deg(v)\) of a node \(v\) can then be defined as the number of nodes connected to that node, _i.e._, its neighborhood size: \(deg(v)=|N(v)|\). The _eccentricity_\(\varepsilon(v)\) of a node \(v\in V\) is defined as the length of a longest shortest path from \(v\) to any other node: \(\varepsilon(v)=\max_{w\in V}d(v,w)\). The _eccentricity distribution_ counts the frequency \(f(x)\) of each eccentricity value \(x\), and can easily be derived when the eccentricity of each node in the graph is known. The _relative eccentricity distribution_ lists for each eccentricity value \(x\) its relative frequency \(F(x)=f(x)/n\), normalizing for the number of nodes in the graph. Figure 1 shows the relative eccentricity distributions of a number of large graphs (for a detailed description of these datasets, see Section 6.1). Figure 1: Relative eccentricity distributions of various large graphs. Various other measures can be derived using the notion of eccentricity, such as the _average eccentricity_\(\overline{\varepsilon}(G)\) of a graph \(G\), defined as \(\overline{\varepsilon}(G)=\frac{1}{n}\sum_{v\in V}\varepsilon(v)\). Another related measure is the _diameter_\(\Delta(G)\) of a graph \(G\), which is is defined as the maximum eccentricity over all nodes in the graph: \(\Delta(G)=\max_{v\in V}\varepsilon(v)\). Similarly, we define the _radius_\(\Gamma(G)\) of a graph \(G\) as the minimum eccentricity over all nodes in the graph: \(\Gamma(G)=\min_{v\in V}\varepsilon(v)\). The graph center \(C(G)\) refers to the set of nodes with an eccentricity equal to the radius, \(C(G)=\{v\in V\mid\varepsilon(v)=\Gamma(G)\}\). Similarly, the graph periphery \(D(G)\) is defined as the set of nodes with an eccentricity value equal to the diameter of the graph: \(D(G)=\{v\in V\mid\varepsilon(v)=\Delta(G)\}\). Each of the measures explained above can be derived when the eccentricity of all nodes is known. Figure 2 shows an example of a graph that explains the different measures covered in this section. Computing the eccentricity of one node can be done by running [PERSON]'s algorithm, and returning the largest distance found (_i.e._, the distance to a node furthest away from the starting node). Because we only consider unweighted graphs and thus, starting from the current node, can simply explore the neighboring nodes in level-order, computing the eccentricity of one node can be done in \(O(m)\) time. The process of determining the eccentricity of one node \(v\) is denoted by \(\textsc{Eccentricity}(v)\) in Algorithm 1. ```
1:Input: Graph \(G(V,E)\)
2:Output: Vector \(\varepsilon\), containing \(\varepsilon(v)\) for all \(v\in V\)
3:for\(v\in V\)do
4:\(\varepsilon[v]\leftarrow\textsc{Eccentricity}(v)\) // \(\circ\)(m)
5:endfor
6:return\(\varepsilon\)
```  
**Algorithm 1**NaiveEccentricities  
This algorithm simply computes the eccentricity for each of the \(n\) nodes, resulting in an overall complexity of \(O(mn)\) to determine the eccentricity of every node in the graph.