The complex network problem

From InterSciWiki

Jump to: navigation, search

[Network analysis] includes analysis of structure, such as the two well-known complex network models:

  • scale-free network, generated probabilistically by preferential attachment
  • 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.

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 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.

Contents

[edit] Bibliography

Reviewed 2005 in Europhysicsnews 36(6):218-220 by Stefan Thurner.

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 http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test.

[edit] Implementations

Python_for_networks#Illustration:_Generating_Social_circles_feedback_networks by Nataša Kejžar

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.

[edit] OSG

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.

[edit] Links

Retrieved from "http://intersci.ss.uci.edu/wiki/index.php/The_complex_network_problem"
Personal tools