Jan 26, 2012
from 02:00 PM to 03:00 PM
|Where||Keynes Hall, King's College|
|Add event to calendar||
Vincenzo Nicosia (Computer Laboratory, University of Cambridge, UK and Laboratory on Complex Systems, Scuola Superiore di Catania, Italy):
Controlling centrality in complex networks
Node and edge centrality have a pivotal importance in the study and characterization of complex networks, and nowadays centrality measures are widely used to identify influential individuals in social groups, to rank Web pages by popularity, and even to determine the impact of scientific research. Many different structural properties have been used to assess the importance of nodes, but in most of the cases the centrality of every single node crucially depends on the entire pattern of connections. Therefore, the usual approach is to compute node centralities once the network structure is assigned. We discuss here a solution to the so-called "inverse centrality problem", which consists into controlling the centrality scores of the nodes by opportunely acting on the structure of a given network. In particular, we focus our attention on spectral centrality measures and we show that there exist particular subsets of nodes, called controlling sets, which can assign any prescribed set of centrality values to all the nodes of a graph, by cooperatively tuning the weights of their out-going links. We found that many large networks from the real world have surprisingly small controlling sets, containing even less than 5-10% of the nodes. Consequently, the rankings obtained by spectral centrality measures should be taken into account with extreme care, since they can be easily manipulated and even distorted by small groups of malicious nodes acting cooperatively.
References:  V. Nicosia, R. Criado. M. Romance, G. Russo and V. Latora "Controlling centrality in complex networks" Scientific Reports 2, 218 (2012), doi:10.1038/srep00218 http://www.nature.com/srep/2012/120111/srep00218/full/srep00218.html
Eiko Yoneki (Computer Laboratory, University of Cambridge, UK):
On Joint Diagonalisation for Dynamic Network Analysis
Joint diagonalisation (JD) is a technique used to estimate an average eigenspace of a set of matrices. Whilst it has been used successfully in many areas to track the evolution of systems via their eigenvectors; its application in network analysis is novel. The key focus is the use of JD on matrices of spanning trees of a network. This is especially useful in the case of real-world contact networks in which a single underlying static graph does not exist. The average eigenspace may be used to construct a graph which represents the `average spanning tree' of the network or a representation of the most common propagation paths. We then examine the distribution of deviations from the average and find that this distribution in real-world contact networks is multi-modal; thus indicating several modes in the underlying network. These modes are identified and are found to correspond to particular times. Thus JD may be used to decompose the behaviour, in time, of contact networks and produce average static graphs for each time. This may be viewed as a mixture between a dynamic and static graph approach to contact network analysis.