Evolving Networks with Distance Preferences

Jost and Joy

@article{jost:pre-2002,
  title={Evolving Networks with Distance Preferences},
  author={Jost, J. and Joy, MP},
  journal={Physical Review E},
  volume={66},
  number={3},
  year={2002},
  publisher={APS}
}

Studies networks grown using various link creation functions based on distance

• Shows that shortest-distance function can develop networks w/ power law degree distribution similar to scale free networks, but differing in other characteristics, particularly clustering coefficient

Most real world graphs show some kind of regularity

• Perhaps not in specific patterns, but as demonstrated in one or more metrics
  • Clustering coefficient
  • Maximal distance
  • Degree distribution
  • Correlation of these properties among neighbors
• The first eigenvalue of the graph, which is related to synchronization

Relevant types of graphs:

• Regular graphs: Each node has same connectivity pattern, degree
• Random graphs: Links are chosen completely randomly
• Small world graphs (Watts & Strogatz): Regular graphs with additional random links and possibly some deletions
• Scale free graphs (Barabasi & Albert): New nodes link to previous nodes w/ a bias for better connected nodes

Construction presented here is similarly simple but based on distance

• New nodes are connected at random to an existing node
• It is then linked to $m$ other nodes; in paper, m = $m_0$, the initial network size
• Links are determined via a distance preference function
• Note that each link changes the world and affects the subsequent selections

Distance preference functions may be deterministic or probabilistic; examples:

• Shortest distance: Only select nodes 2 hops away
• Greatest distance: Only select nodes at maximal distance
• Short preference: Probability proportional to inverse distance
• Long preference: Probability proportional to distance

Some of the distance preference functions require relatively local information

• Particularly as opposed to standard scale free construction
• Particularly when only shortest distances are allowed

Simulations look at metrics using several network constructions:

• Triangular, in which only shortest links are used
• Short, in which probability is inversely proportional to distance
• Long, in which probability is proportional to distance
• Random
• Scale Free

Various results from simulation show:

• Synchronization in triangular construction is difficult (low eigenvalue of Laplacian), which could be useful or not
• Scale free model has highest eigenvalue, entailing relatively easy synchronization
• Triangular model has high clustering coefficient, while others are relatively low
• Biasing links toward nodes at larger distances is not as efficient in reducing maximal distance as biasing toward well connected nodes
• Biasing toward short distances leads to larger average distance, but not severely so
• Triangular model produces a power law degree distribution

Of note:

• Other models discussed include Klemm and Eguiluz, in which older nodes become inactive at same rate as new nodes are added; produces highly clustered networks