# The complex network problem

Wikipedia:Network analysis includes analysis of structure, such as the two well-known complex network models and a third less well-known:

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

- http://intersci.ss.uci.edu/wiki/pub/feedback.py
- http://intersci.ss.uci.edu/wiki/pub/to_Pajek.py
- Use the python shell to open and run feedback.py don't just click on it or you won't see any error messages.

## Contents

## Bibliography

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

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 Wikipedia:Kolmogorov-Smirnov_test.

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

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

import sets

will be followed by fairly long computation time for 5000 nodes.

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

- Homepage: http://pypi.python.org/pypi/osg/
- Source Repository: http://www.irl.styx.org/hgweb.py/osg/

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

## Links

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