Summary
Abstract 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 singledimension 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.
Relevance for Complex Systems Knowledge
This article demonstrates ways of making network analysis through multidimension relations between the components. Most real-life networks are intrinsically multidimensional, and some of their properties may be lost if the different dimensions are not taken into account. Traditional network analytical measures come under a different light when seen in the multidimensional setting, since the analysis scenario gets even richer, thanks to the availability of different dimensions to take into account. The article extended traditional network metrics , broadly used in social/complex network analysis and graph theory, to the multidimensional case and introduced brand new ones, which exploit explicitly the multiple dimensionality – and therefore only make sense in the multidimensional case.
