Modeling the Small-World Phenomenon with Local Network Flow
Andersen, Reid ; Chung, Fan ; Lu, Linyuan
Internet Math., Tome 2 (2005) no. 2, p. 359-385 / Harvested from Project Euclid
The small-world phenomenon includes both small average distance and the clustering effect. Randomly generated graphs with a power law degree distribution are widely used to model large real-world networks, but while these graphs have small average distance, they generally do not exhibit the clustering effect. We introduce an improved hybrid model that combines a global graph (a random power law graph) with a local graph (a graph with high local connectivity defined by network flow). We present an efficient algorithm that extracts a local graph from a given realistic network. We show that the underlying local graph is robust in the sense that when our extraction algorithm is applied to a hybrid graph, it recovers the original local graph with a small error. The proof involves a probabilistic analysis of the growth of neighborhoods in the hybrid graph model.
Publié le : 2005-05-14
Classification: 
@article{1150474887,
     author = {Andersen, Reid and Chung, Fan and Lu, Linyuan},
     title = {Modeling the Small-World Phenomenon with Local Network Flow},
     journal = {Internet Math.},
     volume = {2},
     number = {2},
     year = {2005},
     pages = { 359-385},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1150474887}
}
Andersen, Reid; Chung, Fan; Lu, Linyuan. Modeling the Small-World Phenomenon with Local Network Flow. Internet Math., Tome 2 (2005) no. 2, pp.  359-385. http://gdmltest.u-ga.fr/item/1150474887/