Definitions

The clustering algorithm uses neighbor sets, a boolean notion of one AS being a potential parent of another AS, a distance function that acts as the length of a link and an overhang function that measures the amount by which a potential parent fails to completely dominate a child.

The following definitions are used throughout the paper:

• $AS_n$ is a neighbor of $AS_m$ if it immediately follows or precedes $AS_m$ in any best path. To simplify the algorithm, $AS_n$ is always added to its own list of neighbors.

• The set of neighbors of $AS_n$ is denoted by $N_n$. The parent of $AS_n$ is $p(n)$, initially $0$.

• The out-degree, $outdegree(n)$ is the initial $\vert N_n\vert$. The original out-degree is preserved for the AS. The out-degree of a cluster is the out-degree of its exemplar.

• $AS_n$ is said to dominate $AS_m$ if $N_n \supset N_m$. In particular,
  
  $$dom(n,m) \equiv ( N_n \setminus N_m = \emptyset ) \wedge ( N_m \setminus N_n \not= \emptyset )$$
  
  

• The Hamming distance between $AS_n$ and $AS_m$ is the number of neighbors exclusive to only one of them.
  
  $$dist(n,m) \equiv \vert N_n \cup N_m\vert - \vert N_n \cap N_m\vert$$
  
  

• The overhang of $AS_n$ over $AS_m$ is the size of the set of Neighbors of $n$ who are not also Neighbors of $m$.
  
  $$overhang(n,m) \equiv \vert N_n \setminus N_m\vert$$