Foundations of Multidimensional Network Analysis

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

Graph Theory  Database Applications  Multidimensional network analysis  Social Network  Complex Network 

Complex networks have been receiving increasing attention by the scientific community, also due to the availability of massive network data from diverse domains, and the outbreak of novel analytical paradigms, which pose relations and links among entities, or people, at the center of investigation. Networks are usually modeled by graphs. So far, network analytics has focused to the characterization and measurement of local and global properties of such graphs, such as diameter, degree distribution, centrality, connectedness - up to more sophisticated discoveries based on graph mining, aimed at finding frequent subgraph patterns and analyzing the temporal evolution of a network. However, in practice, real networks come with a rich semantics attached to relations, and nodes in a network may be connected by edges of different nature: for example, any given pair of persons may communicate with different tools (phone, email, messaging, etc), or in a social network can be linked by a different relation (being friends, colleagues, relatives, etc). A network where several possible connections (edges) exist between the same pair of entities (nodes) is called a multidimensional network. Despite the importance of this kind of network is recognized in many works, and ad-hoc analytical means have been proposed to deal with multidimensional networks of specific cases, a thorough systematic framework for multidimensional network analysis is still missing. This is precisely the aim of this paper: we develop a solid repertoire of basic concepts and analytical mechanisms, which takes into account the general structure of multidimensional networks: first, we model a multidimensional network as a multigraph, i.e., a graph where nodes can be connected by one or more labeled edges; second, we systematically develop a vast repertoire of network metrics for the graph, to characterize local and global properties of multidimensional networks. We show how popular measures like the degree of a node, the number of connected components in a graph, the shortest path, and so on, can be viewed as particular cases of more general definitions for multidimensional networks. Further, we introduce brand new metrics for multigraphs, that take into consideration the interplay among different dimension, and therefore have no counterpart in the single- dimension case. In order to demonstrate the usefulness and wide applicability of the proposed framework, we consider a large array of massive networks in diverse domains, ranging from query logs to social networks, customer networks, subgraphs and bibliographic networks, and show how in each such case the introduced metrics - both the generalization of the known ones and the brand new multidimensional metrics - reveal a surprising high analytical power and suggest novel solutions to challenging real life problems.

Source: ISTI Technical reports, 2010