|
|
An Exploration of Power-Law Networks
Part IV: Summary
Owen Densmore
Sun Microsystems Laboratories
owen.densmore@sun.com |
|
Summary
This study starts with four milestone papers which:
-
Identify the Small World, Local Knowledge Search phenomenon
-
Create a graph theoretic framework for understanding Small Worlds Networks
-
Introduce Power-Law network features, via dynamic formation with preferential
binding.
-
Discover a means for searching in Power-Law networks
As this theoretical framework was solidifying, a dynamic new computing
technique, Peer to Peer systems, was surfacing. These two areas are starting
to be bridged by efforts such as Clip2's analysis of Gnutella, and Freenet's
Theodore Hong applying these techniques to performance in peer systems.
To better understand these methods, an exploration was devised, including:
-
The creation of 1890 datasets for 11 classes of Power-Law networks.
-
Four structured Power-List networks: TdL+/-, TdS+/-
-
Four random Power-List networks: RdE+/-, RdN+/-
-
Three Generated networks: SmW+/-, Bag
-
Building network graphs for the 810 smaller networks (node counts of 25,
50, 100)
-
Creating 3 sets of 540 data plots for the 1000 and 2000 node networks.
These include
-
An edge histogram with power-law fit
-
A search plot comparing Power-Law, Depth First and Breadth First searches
(radius 3)
-
A level histogram, showing the distance distribution from the most populous
node
-
A series of summary graphs (Class plots, Family plots, Summary plots) for
studying groups of networks.
Overall, the results strongly support the use of statistical, complex systems
methods for studying self organizing Peer networks.
-
Power-Law searching performs quite well, even among widely divergent network
topologies.
-
Graph theoretic metrics such as Clustering Coefficient, Characteristic
Path, Diameter, Traversal Levels, Sample Searches and others offer useful
tools for characterizing peer networks.
-
Visualization techniques such as network plots (edge and level histograms,
search), network graphs, and summary plots (Family, Class, etc.) allow
quick and varied navigation of these large datasets.
-
Web organization of large datasets further increases the ability to understand
these sets by rapid navigation of the hyperlinked data.
Future Directions
This is clearly just the start of the interesting exploration of Small
Worlds and Power-Law Networks as applied to Peer Networking. Future
directions include:
-
Jxta: Conversations with the JXTA
Project team point out that their search/discovery subsystem is quite
modular and thus can be used to implement research ideas such as these.
An evaluation of a Jxta related project is underway.
-
MetaData: The current Power-Law search has no notion of meta-data;
yet the original Milgram experiment had knowledge of the target: Sex, Age,
Geographic Location, Occupation, and so on. One participant might
be familiar with several doctors, thus would favor delivery to a well connected
doctor, regardless of location. Another participant could easily
know several well connected people in the general geographical area.
Each of these meta-data components themselves may easily exhibit Power-Law
behavior and form a cluster of search channels. It would be interesting
to integrate such meta-data into further studies.
-
Simulation: Variation over time is a key feature of peer networks.
This exploration began with the use of the Repast
simulation software in the Local Knowledge Networking Project.
As detailed as the present study is, simulation adds the dimension of time
to study of Peer Networks. The results of this exploration
will be integrated with the earlier simulation work.
-
Additional Parameters: A key pair of missing network parameter is
bandwidth and latency. Further study should include weighted edges,
possibly directed, for building more realistic networks.
-
Existing Networks: There is now data for existing networks.
It would be valuable to include this into future work.
-
Topology Management: The study found poorly performing network topologies.
A future project may look at how to slightly modify them to regain performance.
-
New Results: New papers have shown additional network types and
search methods. Promising work may be integrated into this study
in the near future.
Thanks
This project grew from a suggestion made by Laura Hill. Technical
support, encouragement, and review came from the Complexity Lunch Group:
Randy Smith, Helen Cunningham, Achut Reddy and Raphael Rom.
Links and References
The Four Papers:
Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani,
and Bernardo A. Huberman:
Search
in Power-Law Networks
http://www.hpl.hp.com/research/idl/papers/plsearch/
Albert-László Barabási,
Réka Albert, and Hawoong Jeong: Mean-field
Theory for Scale-Free Random Networks
Physica A 272 173-187 (1999) http://www.nd.edu/~networks/papers.htm#paper3
Stanley Milgram: The
Small World Problem, Psychology Today 1(1), 60-67 (1967)
http://citeseer.nj.nec.com/context/302442/0. See also:
The Individual
in a Social World: Essays and Experiments, pp. 281-295. Addison-Wesley.
Duncan J. Watts, Steven H. Strogatz. Collective
Dynamics of 'Small-World' Networks.
Nature 393, 440-442 (1998). See also:
Small Worlds
Princeton Univ Pr; ISBN: 0691005419 August 23, 1999
Note: The latter two papers are not available on-line. The Small
Worlds book is readily available and covers the same material and considerably
more. Milgram's paper appears in the sited collection.
Other
Owen Densmore. Local Knowledge Networking Project: Project
Page and References.
Brian Hayes. American Scientist Graph Theory Tutorial: Part
1 and Part
2
American Scientist, V88 No. 1 & 2. 2000
Theodore Hong. Performance
Peer-to-Peer:
Harnessing the Power of Disruptive Technologies, ed. by A Wram.
O'Reilly and Associates: Sebastopol, CA.
Kelly Truelove, Clip2. Gnutella:
To the Bandwidth Barrier and Beyond
