The complex network problem
- Wikipedia:Scale-free_network, generated probabilistically by preferential attachment
- Wikipedia:Small-world_network, studied by taking a highly clustered network and randomly rewiring edges. observe the rapid drop in average distance but slow drop in clustering.
- Social-circles network feedback model
One problem with simpler complex network models is that the more broadly applicable they are in terms of binary features (clustering, shorter distances that expected at random) the less informative they are for real world network, as with the small-world model. Another is that the more stylized they are, like the preferential attachment (Scale-free) model, the more ambiguous is the interpretation of what actual processes might have generated similar outcomes.
Doug white explores the questions posed by the generative feedback network or Wikipedia:Social-circles_network_model, which generates heavy-tails in simulated degree distributions, greater than random clustering coefficients, community and hierarchical structure, complex routing structures, and, waiting to be explored, possibly many other features of complex networks. This model has a few fundamental generating parameters that generate a wide variety of complex network variants with similarities to many different types of real world networks. When the node activity parameter is positive, for example, so that current activity scales according to past activity, or when the routing parameter for feedback in the network is positive , so that routing through hubs scales preferentially according to degree, the degree distributions acquire heavy-tails.
- Use the python shell to open and run feedback.py don't just click on it or you won't see any error messages.
- "Generative Model for Feedback Networks" in Physical Review E, 016119 (2006, Douglas R. White, Wikipedia:Nataša Kejžar, Constantino Tsallis, Wikipedia:J. Doyne Farmer, Scott D. White. Final paper in pdf as SFI working paper.
The Kolmogorov-Smirnov test or KS-test is used in this article to compare actual degree distributions to best-fit distributions using the q-exponental (Tsallis entropy). It is also discussed in Wikipedia:Kolmogorov-Smirnov_test.
An interesting point out of these discussions is whether, when the search lands on a point already connected as a partner, a new external edge should be created.
In python: click feedback.py from the Python directory (e.g., \Python26) after Python and Networkx are installed. A DOS window will open. The message
will be followed by fairly long computation time for 5000 nodes.
An implementation called OSG of Django (Python) models and views by William Waites for representing nodes and edges in a directed graph, managing node and edge metadata as well as the first cut at support for Google's OpenSocial Data API. It is intended to form part of a toolkit for people wishing to implement web sites and services using Django that make use of concepts of social networking and graph theory. It is informed by research and discussion surrounding the Ripplepay network. It contains a manager implementation of this generative algorithm in the file osg/feedback.py. Source code is available from the Python Cheese Shop or in the Mercurial Repository at Idiosyntactix Research Laboratories.
There is a gallery of graphs generated using this software for viewing on the web.
Known potential problems with the OSG implementation:
* Since the path search is not exhaustive, that is at each step outwards from the starting node a single adjacent node is chosen for the next step, it is possible to arrive at the desired distance and find a node that has an edge connecting it to the start node. What to do in this case? Create a new node? Consider the search successful and proceed to the next iteration? This implementation does the latter.
- Simulated data in a Pajek Network Project *.paj file for 1250 nodes paramaters 0-2-0
- Walk-through of a network simulation, edge by edge with the same parameters
- A good review of small-world and scale-free models for complex networks is found in statistical mechanics of social networks by Albert and Barabasi 2001 published in Rev. Mod. Phys., Vol. 74, No. 1, January 2002.