Multidimensional network

Multidimensional networks are networks with multiple kinds of relations.^[1] Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis,^{[2][3][4][5][6]} economics, urban and international transport,^[7][8][9] ecology, psychology,^[10] medicine, biology,^[11] commerce, climatology, physics,^[12][13] operations management, and finance.

Terminology

The rapid exploration of complex networks in recent years has been dogged by a lack of standardized naming conventions, as various groups use overlapping and contradictory^[14][15] terminology to describe specific network configurations (e.g., multiplex, multilayer, multilevel, multidimensional, multirelational, interconnected). Formally, multidimensional networks are edge-labeled multigraphs.^[16] The term "fully multidimensional" has also been used to refer to a multipartite edge-labeled multigraph.^[17] Multidimensional networks have also recently been reframed as specific instances of multilayer networks.^[18][19][20] In this case, there are as many layers as there are dimensions, and the links between nodes within each layer are simply all the links for a given dimension.

Model

Core elements

In elementary network theory, a network is represented by a graph $G = (V,E)$ in which $V$ is the set of nodes and $E$ the links between nodes, typically represented as a tuple of nodes $u,v\in V$. While this basic formalization is useful for analyzing many systems, real world networks often have added complexity in the form of multiple types of relations between system elements. The earliest formalizations of this idea came through its application in the field of social network analysis,^[21] in which multiple forms of social connection between people were represented by multiple types of links.^[22]

To accommodate the presence of more than one type of link, a multidimensional network is represented by a triple $G = (V,E,D)$, where $D$ is a set of dimensions, each member of which is a different type of link, and $E$ consists of triples $(u,v,d)$ with $u,v\in V$ and $d\in D$.^[20]

Extensions

In the case of a weighted network, this triplet is expanded to a quadruplet $e = (u,v,d,w)$, where $w$ is the weight on the link between $u$ and $v$ in the dimension $d$.

The multiplex network of European airports. Each airline denotes a different layer. Visualization made with the muxViz software

Further, as is often useful in social network analysis, link weights may take on positive or negative values. Such signed networks can better reflect relations like amity and enmity in social networks.^[17] Alternatively, link signs may be figured as dimensions themselves,^[23] e.g. $G = (V,E,D)$ where $D=\{-1,0,1\}$ and $E = \{(u,v,d); u,v \in V, d \in D\}$ This approach has particular value when considering unweighted networks.

This conception of dimensionality can be expanded should attributes in multiple dimensions need specification. In this instance, links are n-tuples $e = (u,v,d_1 \dots d_{n-2})$. Such an expanded formulation, in which links may exist within multiple dimensions, is uncommon but has been used in the study of multidimensional time-varying networks.^[24]

Comments

The World Economic Forum map of global risks and global trends, modeled as an interdependent network (also known as network of networks). Visualization made with the muxViz software

Note that as in all directed graphs, the links $(u,v,d)$ and $(v,u,d)$ are distinct.

By convention, the number of links between two nodes in a given dimension is either 0 or 1 in a multidimensional network. However, the total number of links between two nodes across all dimensions is less than or equal to $|D|$.

Multidimensional network-specific parameters

Attributes

Multi-layer adjacency tensor

Whereas unidimensional networks have two-dimensional adjacency matrices of size $V\times V$, in a multidimensional network with $D$ dimensions, the adjacency matrix becomes a multilayer adjacency tensor, a four-dimensional matrix of size $V\times D\times V\times D$.^[3] As in unidimensional matrices, directed links, signed links, and weights are all easily accommodated by this framework.

The multiplex social network of Star Wars saga. Each layer denotes a different episode and two nodes are connected each other if the corresponding characters acted together in one or more scenes. Visualization made with muxViz software

Multi-layer neighbors

In a multidimensional network, the neighbors of some node $v$ are all nodes connected to $v$ across dimensions.

Multi-layer path length

A path between two nodes in a multidimensional network can be represented by a vector r $=(r_1, \dots r_{|D|})$ in which the $i$th entry in r is the number of links traversed in the $i$th dimension of $G$.^[25] As with overlapping degree, the sum of these elements can be taken as a rough measure of a path length between two nodes.

Measures

Degree

In a multidimensional network, the degree of a node is represented by a vector of length $|D|: \bold{k} = (k^{1}_i,\dots k^{|D|}_i)$. However, for some computations it may be more useful to simply sum the number of links adjacent to a node across all dimensions.^[3][26] This is the overlapping degree: $\sum_{\alpha = 1}^{|D|} k^{\alpha}_i$. As with unidimensional networks, distinction may similarly be drawn between incoming links and outgoing links.

Degree correlations

The question of degree correlations in unidimensional networks is fairly straightforward: do networks of similar degree tend to connect to each other? In multidimensional networks, what this question means becomes less clear. When we refer to a node's degree, are we referring to its degree in one dimension, or collapsed over all? When we seek to probe connectivity between nodes, are we comparing the same nodes across dimensions, or different nodes within dimensions, or a combination?^[20] What are the consequences of variations in each of these statistics on other network properties? In one study, assortativity was found to decrease robustness in a duplex network.^[27]

Clustering coefficients

Like many other network statistics, the meaning of a clustering coefficient becomes ambiguous in multidimensional networks, due to the fact that triples may be closed in different dimensions than they originated.^[18] Several attempts have been made to define local clustering coefficients, but these attempts have highlighted the fact that the concept must be fundamentally different in higher dimensions: some groups have based their work off of non-standard definitions,^[28] while others have experimented with different definitions of random walks and 3-cycles in multidimensional networks.^[29]

Community discovery

While cross-dimensional structures have been studied previously,^[30][31] they fail to detect more subtle associations found in some networks. Taking a slightly different take on the definition of "community" in the case of multidimensional networks allows for reliable identification of communities without the requirement that nodes be in direct contact with each other.^{[2][3][5][32]} For instance, two people who never communicate directly yet still browse many of the same websites would be viable candidates for this sort of algorithm.

Path dominance

Given two multidimensional paths, r and s, we say that r dominates s if and only if: $\forall d\in \langle 1,|D|\rangle , r_l \leq s_l$ and $\exists i$ such that $r_l < s_l$.^[25]

Shortest path discovery

Among other network statistics, many centrality measures rely on the ability to assess shortest paths from node to node. Extending these analyses to a multidimensional network requires incorporating additional connections between nodes into the algorithms currently used (e.g., Dijkstra's). Current approaches include collapsing multi-link connections between nodes in a preprocessing step before performing variations on a breadth-first search of the network.^[14]

Multidimensional distance

One way to assess the distance between two nodes in a multidimensional network is by comparing all the multidimensional paths between them and choosing the subset that we define as shortest via path dominance: let $MP(u,v)$ be the set of all paths between $u$ and $v$. Then the distance between $u$ and $v$ is a set of paths $P\subseteq MP$ such that $\forall p\in P, \nexists p'\in MP$ such that $p'$ dominates $p$. The length of the elements in the set of shortest paths between two nodes is therefore defined as the multidimensional distance.^[25]

Dimension relevance

In a multidimensional network $G = (V,E,D)$, the relevance of a given dimension (or set of dimensions) $D'$ for one node can be assessed by the ratio: $\frac{\text{Neighbors}(v,D')}{\text{Neighbors}(v,D)}$.^[26]

Dimension connectivity

In a multidimensional network in which different dimensions of connection have different real-world values, statistics characterizing the distribution of links to the various classes are of interest. Thus it is useful to consider two metrics that assess this: dimension connectivity and edge-exclusive dimension connectivity. The former is simply the ratio of the total number of links in a given dimension to the total number of links in every dimension: $\frac{|\{(u,v,d)\in E | u,v\in V\}|}{|E|}$. The latter assesses, for a given dimension, the number of pairs of nodes connected only by a link in that dimension: $\frac{|\{(u,v,d)\in E | u,v\in V \wedge \forall j\in D,j\neq d: (u,v,j)\notin E\}|}{|\{(u,v,d)\in E | u,v\in V\}|}$.^[26]

Burst detection

Burstiness is a well-known phenomenon in many real-world networks, e.g. email or other human communication networks. Additional dimensions of communication provide a more faithful representation of reality and may highlight these patterns or diminish them. Therefore it is of critical importance that our methods for detecting bursty behavior in networks accommodate multidimensional networks.^[33]

References

1. Coscia, Michele; Rossetti, Giulio; Pennacchioli, Diego; Ceccarelli, Damiano; Giannotti, Fosca (2013). ""You Know Because I Know": A Multidimensional Network Approach to Human Resources Problem" (PDF). Advances in Social Network Analysis and Mining (ASONAM) 2013. arXiv:1305.7146. doi:10.1145/2492517.2492537.
2. Mucha, P.; et al. (2010). "Community structure in time-dependent, multiscale, and multiplex networks" (PDF). Science 328 (5980): 876–878. arXiv:0911.1824. doi:10.1126/science.1184819.
3. De Domenico, M.; Solé-Ribalta, A.; Cozzo, E.; Kivelä, M.; Moreno, Y.; Porter, M.; Gómez, S.; Arenas, A. (2013). "Mathematical Formulation of Multilayer Networks" (PDF). Physical Review X 3 (4). doi:10.1103/PhysRevX.3.041022.
4. Battiston, F.; Nicosia, V.; Latora, V. (2014). "Structural measures for multiplex networks" (PDF). Physical Review E 89: 032804. doi:10.1103/PhysRevX.3.041022.
5. De Domenico, M.; Lancichinetti, A.; Arenas, A.; Rosvall, M. (2015). "Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems". Physical Review X 5: 011027. arXiv:1408.2925. doi:10.1103/PhysRevX.5.011027.
6. De Domenico, M.; Sole-Ribalta, A.; Omodei, E.; Gomez, S.; Arenas, A. (2015). "Ranking in interconnected multilayer networks reveals versatile nodes". Nature Communications 6: 6868. doi:10.1038/ncomms7868.
7. Cardillo, A.; et al. (2013). "Emergence of network features from multiplexity". Scientific Reports 3: 1344. doi:10.1038/srep01344.
8. Gallotti, R.; Barthelemy, M. (2014). "Anatomy and efficiency of urban multimodal mobility". Scientific Reports 4: 6911. arXiv:1411.1274. doi:10.1038/srep06911.
9. De Domenico, M.; Sole-Ribalta, A.; Gomez, S.; Arenas, A. (2014). "Navigability of interconnected networks under random failures". PNAS 111: 8351. doi:10.1073/pnas.1318469111.
10. Fiori, K. L.; Smith, J; Antonucci, T. C. (2007). "Social network types among older adults: A multidimensional approach". The journals of gerontology. Series B, Psychological sciences and social sciences 62 (6): P322–30. PMID 18079416.
11. De Domenico, M.; Nicosia, V.; Arenas, A.; Latora, V. (2015). "Structural reducibility of multilayer networks". Nature Communications 6: 6864. doi:10.1038/ncomms7864.
12. Gao; Buldyrev; Stanley; Havlin (22 December 2011). "Networks formed from interdependent networks". Nature Physics 8, 40–48 (2012). doi:10.1038/nphys2180.
13. De Domenico, M.; Granell, C.; Porter, Mason A.; Arenas, A. (7 April 2016). "The physics of multilayer networks". arXiv:1604.02021.
14. Bródka, P.; Stawiak, P.; Kazienko, P. (2011). "Shortest Path Discovery in the Multi-layered Social Network". 2011 International Conference on Advances in Social Networks Analysis and Mining. pp. 497–501. doi:10.1109/ASONAM.2011.67. ISBN 978-1-61284-758-0.
15. Barrett, L.; Henzi, S. P.; Lusseau, D. (2012). "Taking sociality seriously: The structure of multi-dimensional social networks as a source of information for individuals". Philosophical Transactions of the Royal Society B: Biological Sciences 367 (1599): 2108. doi:10.1098/rstb.2012.0113. PMC 3385678. PMID 22734054.
16. Zignani, Matteo; Quadri, Christian; Gaitto, Sabrina; Gian Paolo Rossi (2014). "Exploiting all phone media? A multidimensional network analysis of phone users' sociality". arXiv:1401.3126 [cs.SI].
17. Contractor, Noshir, Peter Monge, & Paul M. Leonardi. "Network Theory | Multidimensional Networks and the Dynamics of Sociomateriality: Bringing Technology Inside the Network". International Journal of Communication, 5 (2011): 39. Retrieved 26 November 2014
18. Kivela, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A. (2014). "Multilayer networks". Journal of Complex Networks 2 (3): 203. doi:10.1093/comnet/cnu016.
19. Magnani, M.; Rossi, L. (2011). "The ML-Model for Multi-layer Social Networks". 2011 International Conference on Advances in Social Networks Analysis and Mining. p. 5. doi:10.1109/ASONAM.2011.114. ISBN 978-1-61284-758-0.
20. Boccaletti, S.; Bianconi, G.; Criado, R.; del Genio, C. I.; Gómez-Gardeñes, J.; Romance, M.; Sendiña-Nadal, I.; Wang, Z.; Zanin, M. (2014). "The structure and dynamics of multilayer networks" (PDF). Physics Reports 544 (1): 1. arXiv:1407.0742. doi:10.1016/j.physrep.2014.07.001.
21. Goffman. Frame analysis: an essay on the organization of experience. ISBN 9780930350918.
22. Wasserman, Stanley (1994-11-25). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. ISBN 9780521387071.
23. Leskovec, Jure; Huttenlocher, Daniel; Kleinberg, Jon (2010). "Predicting Positive and Negative Links in Online Social Networks" (PDF). WWW : ACM WWW International conference on World Wide Web 2010 (2010): 641–650. arXiv:1003.2429. doi:10.1145/1772690.1772756.
24. Kazienko, P. A.; Musial, K.; Kukla, E. B.; Kajdanowicz, T.; Bródka, P. (2011). "Multidimensional Social Network: Model and Analysis". Computational Collective Intelligence. Technologies and Applications. Lecture Notes in Computer Science 6922. p. 378. doi:10.1007/978-3-642-23935-9_37. ISBN 978-3-642-23934-2.
25. M. Magnani, A. Monreale, G. Rossetti, F. Giannotti: "On multidimensional network measures", SEBD 2013, Rocella Jonica, Italy
26. Berlingerio, M.; Coscia, M.; Giannotti, F.; Monreale, A.; Pedreschi, D. (2011). "Foundations of Multidimensional Network Analysis". 2011 International Conference on Advances in Social Networks Analysis and Mining (PDF). p. 485. doi:10.1109/ASONAM.2011.103. ISBN 978-1-61284-758-0.
27. Zhou, D.; Stanley, H. E.; d’Agostino, G.; Scala, A. (2012). "Assortativity decreases the robustness of interdependent networks". Physical Review E 86 (6). doi:10.1103/PhysRevE.86.066103.
28. Bródka, Piotr; Kazienko, Przemysław; Musiał, Katarzyna; Skibicki, Krzysztof (2012). "Analysis of Neighbourhoods in Multi-layered Dynamic Social Networks". International Journal of Computational Intelligence Systems 5 (3): 582–596. arXiv:1207.4293. doi:10.1080/18756891.2012.696922.
29. Cozzo, Emanuele; Kivelä, Mikko; Manlio De Domenico; Solé, Albert; Arenas, Alex; Gómez, Sergio; Porter, Mason A.; Moreno, Yamir (2015). "Structure of triadic relations in multiplex networks" (PDF). New Journal of Physics 17: 073029. arXiv:1307.6780 [physics.soc-ph]. doi:10.1088/1367-2630/17/7/073029.
30. Jianyong Wang; Zhiping Zeng; Lizhu Zhou (2006). "CLAN: An Algorithm for Mining Closed Cliques from Large Dense Graph Databases". 22nd International Conference on Data Engineering (ICDE'06) (PDF). p. 73. doi:10.1109/ICDE.2006.34. ISBN 0-7695-2570-9.
31. Cai, D.; Shao, Z.; He, X.; Yan, X.; Han, J. (2005). "Community Mining from Multi-relational Networks". Knowledge Discovery in Databases: PKDD 2005. Lecture Notes in Computer Science 3721. p. 445. doi:10.1007/11564126_44. ISBN 978-3-540-29244-9.
32. Berlingerio, M.; Pinelli, F.; Calabrese, F. (2013). "ABACUS: Frequent p Attern mining-BAsed Community discovery in m Ultidimensional networkS" (PDF). Data Mining and Knowledge Discovery 27 (3): 294–320. arXiv:1303.2025. doi:10.1007/s10618-013-0331-0.
33. Quadri, C.; Zignani, M.; Capra, L.; Gaito, S.; Rossi, G. P. (2014). "Multidimensional Human Dynamics in Mobile Phone Communications". PLoS ONE 9 (7): e103183. doi:10.1371/journal.pone.0103183.

External links