Analysis of hubs in large multidimensional networks

Berlingerio M., Coscia M., Giannotti F., Monreale A., Pedreschi D.

Database Management. Database Applications  Network Analisys 

Hubs in complex networks are important nodes in terms of their connectivity to the whole network. In a mono-dimensional network, i.e., where only one kind of interaction is possible among nodes, the concept of hub has been widely studied, and it is at the basis of many important applications such as web search and epidemic outbreaks. However, in real world scenarios, networks are multidimensional, i.e., several possible kinds of connections exist among the nodes. In this setting, the concept of a hub should take into account the multiple dimensions, that can have varying influence on the connectivity of each node, and whose interplay can be relevant to assess the importance of an entity. In this paper, we tackle the problem of analyzing the relevance of dimensions for node connectivity, and how this relevance analysis can highlight hubs with peculiar, interesting behaviors in a large network. To this end, we consider the multidimensional generalization of the degree, namely the number of neighbors of a node, and a newly introduced class of measures, that we call Dimension Relevance. We show how to efficiently compute these simple measures on one of the possible representations of a multidimensional network, the multigraph. Moreover, we illustrate the usage of our new measures on two different real world networks: a word-word graph built on a search engine query log, and a popular large online social network, Flickr. In both cases, our proposed measures allow us to discover hubs for which one specific dimension is of high relevance and ensures a high connectivity of that node within the network. We advocate that the presented methodology covers a wide range of possible applications, from search engines to computer networks, from biological to social net works, where the interplay among different dimensions can really make the difference for the behavior of specific important entities.

Source: ISTI Technical reports, 2009