University of Otago logo. Computer and Information Science Seminars

Seminar Homepage


Dr Colin Aldridge, Department of Information Science


Scale-Free Networks using Local Information for Preferential Linking


Archway 2 - 1:00 pm, Friday 30 September


Scale-free networks are a recently developed approach to modelling the interactions found in complex natural and man-made systems. Such networks exhibit a power-law distribution of node link (degree) frequencies in which a small number of highly connected nodes predominate over a much greater number of sparsely connected ones.

A recently identified, but now classic example of a scale-free network is the World Wide Web: web pages are nodes. These are connected by hyperlinks. Other examples of such networks traverse disparate fields including scientific paper citations, communications networks and power grids, neural networks, and protein-protein interactions.

The now well-known Albert-Barabási constructive algorithm for constructing scale-free networks centres on the concept of preferential attachment in which the probability of a new node linking to an existing node is proportional to its relative number of links. I contend that when a new node is appended, the global knowledge of node degrees required by Albert-Barabási approach is unrealistic. Instead I propose a locally-derived linking criterion in which only a small part of the total network is considered each time. The Albert-Barabási constructive algorithm then becomes a limiting case of the proposed local algorithm.

I note the existence of 'super hubs' in the extended tail of the connectivity distributions produced by the local preferential linking approach.

Last modified: Thursday, 28-Jul-2005 17:23:30 NZST

This page is maintained by the seminar list administrator.