Dynamics of evolving networks

The network representation of complex systems has been very successful. The key to this success is universality in at least two senses. First, the simplicity of representing complex systems as networks makes it possible to apply network theory to very different systems, ranging from the social structure of a group to the interactions of proteins in a cell. Second, these very different networks show universal structural traits such as the small-world property and the scale-free degree-distribution.

Usually it is assumed that the life of most complex systems is defined by some - often hidden and unknown - underlying governing dynamics. These dynamics are the answers to the question 'How does it work?' and a fair share of scientific effort is taken to uncover this dynamics.

In the network representation the life of a (complex or not) system is modeled as an evolving graph: sometimes new vertices are introduced to the system while others are removed, new edges are formed, others break and all these events are governed by the underlying dynamics.

We've developed a novel methodology to extract the underlying dynamics from the history of the network. The input of this methodology is the network history data and a set of properties which are good candidates for driving the dynamics of the network. These properties can be intrinsic (categories of vertices, vertex age, etc.) or structural (node degree, node transitivity, etc.). The output of the method is one or two functions, the kernel functions which completely describe the stochastic dynamics of the network: the additions and deletions of edges and nodes.

For more information please see the following publications:

• Strandburg KJ, Csárdi G, Tobochnik J, Érdi P, Zalányi L: Law and the Science of Networks: an Overview and an Application to the "Patent Explosion", Berkeley Technology Law Journal, in press (2006)
• Csárdi G, Strandburg, KJ, Zalányi L, Tobochnik J, Érdi P: Modeling innovation by a kinetic description of the patent system, Physica A, in press (2006)
• Csárdi G: Dynamics of citation networks, Proceedings of the International Conference on Artificial Neural Networks, Lecture Notes in Computer Science, 698-709 (2006)
• Csárdi G, Strandburg KJ, Zalányi L, Tobochnik J, Érdi P: Estimating the dynamics of kernel-based evolving networks, Proceedings of the International conference on Complex Systems (2006)

Please contant Gábor Csárdi at csardi(at)rmki(dot)kfki(dot)hu for further information.