Kernels for Complex Networks

Athens.
The second and last day of WebSci '09 starts with a session on social networking, although the first paper in this session, by Yorgos Amanatidis, has the somewhat technical title "Kernels for Complex Networks" - we'll see what that's all about... Visual network graph models, apparently, for graphs which represent relational data in an abstract way. Such graophs can be used in the analysis, simulation, and prediction of network topologies, focussing especially on aspects like scaling, clustering, and node centrality.

What can be observed in real networks is the degree distribution: as the Web grows, the average degree is constant, but there is huge variance and no concentration around the average; indeed, we see the small world phenomenon which produces networks with small diameter and strong clustering tendencies (the friend of my friend is likely also to be my friend). Kleinberg, for example, modelled the fact that in small world networks there are not only short paths between nodes, but that these nodes can find such paths effectively using local information.

There are a number of graph model approaches - including first generation models such as Barabási & Albert's preferential attachment model using power law degrees or Aiello, Chung, & Lu's 'given expected degrees' model. But we want graphs to match real data in their basic metrics (degree distribution and diameter) as well as in further relevant metrics such as hierarchy and clustering (and random graph models tend to fail at this). Clusters and hierarchies are here often determined by very simple semantics.

What is necessary instead is to endow random graphs with semantics, by considering nodes as d-dimensional vectors with one dimension for each attribute (for a graph of internal ISP networks, for example, one could use two dimensions for geometry and a third dimension to represent the hierarchy level of a node - major router, minor router, server). Edge probabilities then depend on sone function of their end points. A natural choice to express similarity is the dot product (mmmh, vector maths - this takes me back...), but there are other options as well, such as kernel functions.

So, what is required are models for complex networks with clear (not ad hoc) parameters, and a wide range of resulting graphs, which are amenable to quantitative analysis. This is essential to study complex networks.

Technorati : Web science, WebSci '09, kernels, mapping, network, vectors, visualisation
Del.icio.us : Web science, WebSci '09, kernels, mapping, network, vectors, visualisation