Multidimensional network: Difference between revisions

Content deleted Content added

Inline

Revision as of 17:50, 26 November 2014

Multidimensional networks are networks with multiple kinds of relations.Cite error: The <ref> tag has too many names (see the help page).

Terminoloy

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^[1]^[2] terminology to describe specific network configurations (e.g., multiplex, multilayer, multilevel, multidimensional, interconnected). Formally, multidimensional networks are edge-labeled multigraphs.^[3] The term "fully multidimensional" has also been used to refer to a multipartite edge-labeled multigraph^[4]. Multidimensional networks have also recently been reframed as specific instances of multilayer networks.^[5] 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^[6], in which multiple forms of social connection between people were represented by multiple types of links. ^[7]

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$ .^[5]

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$ .

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.^[4] Alternatively, link signs may be figured as dimensions themselves,^[8] 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.^[9]

Comments

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

Degree

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

Neighbors

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

Adjacency matrix

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 three-dimensional matrix of size $V\times V\times D$ .^[11]

Multi-layer Path Length

One way to assess the distance between two nodes in a multidimensional network is through 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$ .^[12] As with overlapping degree, the sum of these elements can be taken as a rough measure of distance between two nodes.

Multidimensional distance

Measures

Degree correlations

Clustering coefficients

Community discovery

^[13]

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)}}$ .^[10]

Dimension connectivity

Shortest path discovery

^[1]

Burst detection

^[14]

Path Dominance

Multidimensional betweenness centrality

Applications

Multidimensional network analysis has a wide range of applications.

References

^ ^a ^b Bródka, P., Stawiak, P. & Kazienko, P. (2011). Shortest Path Discovery in the Multi-layered Social Network. ASONAM (p./pp. 497-501), : IEEE Computer Society.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1098/rstb.2012.0113, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1098/rstb.2012.0113 instead.
^ A bot will complete this citation soon. Click here to jump the queue arXiv:1401.3126.
^ ^a ^b 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 [Online], 5 (2011): 39. Web. 26 Nov. 2014
^ ^a ^b A bot will complete this citation soon. Click here to jump the queue arXiv:1407.0742.
^ Goffman. Frame analysis: an essay on the organization of experience. ISBN 9780930350918.
^ Wasserman, Stanley and Katherine Faust. 1994. "Social Network Analysis: Methods and Applications." Cambridge: Cambridge University Press.
^ A bot will complete this citation soon. Click here to jump the queue arXiv:1003.2429.
^ Przemysław Kazienko, Katarzyna Musial, Elżbieta Kukla, Tomasz Kajdanowicz, and Piotr Bródka. 2011. Multidimensional social network: model and analysis. In Proceedings of the Third international conference on Computational collective intelligence: technologies and applications - Volume Part I (ICCCI'11), Piotr Jedrzejowicz, Ngoc Thanh Nguyen, and Kiem Hoang (Eds.), Vol. Part I. Springer-Verlag, Berlin, Heidelberg, 378-387.
^ ^a ^b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/ASONAM.2011.103, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/ASONAM.2011.103 instead.
^ Template:Cite DOI
^ M. Magnani, A. Monreale,G. Rossetti, F. Giannotti: "On multidimensional network measures", SEBD 2013, Rocella Jonica, Italy
^ Template:Cite DOI
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1371/journal.pone.0103183, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1371/journal.pone.0103183 instead.

External links

[Shortest_Path_Discovery_in_the_Multi-layered_Social_Network-1] Bródka, P., Stawiak, P. & Kazienko, P. (2011). Shortest Path Discovery in the Multi-layered Social Network. ASONAM (p./pp. 497-501), : IEEE Computer Society.

[Taking_sociality_seriously:_the_structure_of_multi-dimensional_social_networks_as_a_source_of_information_for_individuals-2] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1098/rstb.2012.0113, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1098/rstb.2012.0113 instead.

[Exploiting_all_phone_media?_A_multidimensional_network_analysis_of_phone_users'_sociality-3] A bot will complete this citation soon. Click here to jump the queue arXiv:1401.3126.

[Network_Theory_|_Multidimensional_Networks_and_the_Dynamics_of_Sociomateriality:_Bringing_Technology_Inside_the_Network.-4] 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 [Online], 5 (2011): 39. Web. 26 Nov. 2014

[The_structure_and_dynamics_of_multilayer_networks-5] A bot will complete this citation soon. Click here to jump the queue arXiv:1407.0742.

[Frame_analysis:_an_essay_on_the_organization_of_experience-6] Goffman. Frame analysis: an essay on the organization of experience. ISBN 9780930350918.

[Social_Network_Analysis:_Methods_and_Applications.-7] Wasserman, Stanley and Katherine Faust. 1994. "Social Network Analysis: Methods and Applications." Cambridge: Cambridge University Press.

[Predicting_Positive_and_Negative_Links_in_Online_Social_Networks-8] A bot will complete this citation soon. Click here to jump the queue arXiv:1003.2429.

[Multidimensional_social_network:_model_and_analysis-9] Przemysław Kazienko, Katarzyna Musial, Elżbieta Kukla, Tomasz Kajdanowicz, and Piotr Bródka. 2011. Multidimensional social network: model and analysis. In Proceedings of the Third international conference on Computational collective intelligence: technologies and applications - Volume Part I (ICCCI'11), Piotr Jedrzejowicz, Ngoc Thanh Nguyen, and Kiem Hoang (Eds.), Vol. Part I. Springer-Verlag, Berlin, Heidelberg, 378-387.

[Foundations_of_Multidimensional_Network_Analysis-10] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/ASONAM.2011.103, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/ASONAM.2011.103 instead.

[Mathematical_Formulation_of_Multilayer_Networks-11] Template:Cite DOI

[On_multidimensional_network_measures-12] M. Magnani, A. Monreale,G. Rossetti, F. Giannotti: "On multidimensional network measures", SEBD 2013, Rocella Jonica, Italy

[ABACUS:_frequent_pAttern_mining-BAsed_Community_discovery_in_multidimensional_networkS-13] Template:Cite DOI

[Multidimensional_Human_Dynamics_in_Mobile_Phone_Communications-14] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1371/journal.pone.0103183, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1371/journal.pone.0103183 instead.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 26: / Line 26: @@
 In a multidimensional network, the neighbors of some node <math>v</math> are all nodes connected to <math>v</math> across dimensions.
 ====Adjacency matrix====
-Whereas unidimensional networks have two-dimensional [[Adjacency matrix|adjacency matrices]] of size <math>V\times V</math>, in a multidimensional network with <math>D</math> dimensions, the adjacency matrix becomes a three-dimensional matrix of size <math>V\times V\times D</math>.<ref name="Mathematical Formulation of Multilayer Networks">{{Cite DOI|10.1103/PhysRevX.3.041022</ref>
+Whereas unidimensional networks have two-dimensional [[Adjacency matrix|adjacency matrices]] of size <math>V\times V</math>, in a multidimensional network with <math>D</math> dimensions, the adjacency matrix becomes a three-dimensional matrix of size <math>V\times V\times D</math>.<ref name="Mathematical Formulation of Multilayer Networks">{{Cite DOI|10.1103/PhysRevX.3.041022}}</ref>
+====Multi-layer Path Length====
+One way to assess the distance between two nodes in a multidimensional network is through a vector '''r''' <math>=(r_1, \dots r_{|D|})</math> in which the <math>i</math>th entry in '''r''' is the number of links traversed in the <math>i</math>th dimension of <math>G</math>.<ref name="On multidimensional network measures">M. Magnani, A. Monreale,G. Rossetti, F. Giannotti: "On multidimensional network measures", SEBD 2013, Rocella Jonica, Italy</ref> As with overlapping degree, the sum of these elements can be taken as a rough measure of distance between two nodes.
+====Multidimensional distance====
 ===Measures===
 ====Degree correlations====
 ====Clustering coefficients====
 ====Community discovery====
 <ref name="ABACUS: frequent pAttern mining-BAsed Community discovery in multidimensional networkS">{{Cite DOI|10.1007/s10618-013-0331-0}}</ref>
 ====Dimension relevance====
-In a multidimensional network, the relevance of a given dimension (or set of dimensions) <math>D</math> for one node can be assessed by the ratio: <math>\frac{\text{neighbors in D}}{\text{neighbors in all dimensions}}</math>.<ref name="Foundations of Multidimensional Network Analysis"/>
+In a multidimensional network <math>G = (V,E,D)</math>, the relevance of a given dimension (or set of dimensions) <math>D'</math> for one node can be assessed by the ratio: <math>\frac{\text{Neighbors}(v,D')}{\text{Neighbors}(v,D)}</math>.<ref name="Foundations of Multidimensional Network Analysis"/>
 ====Dimension connectivity====
 ====Shortest path discovery====
 <ref name="Shortest Path Discovery in the Multi-layered Social Network">Bródka, P., Stawiak, P. & Kazienko, P. (2011). Shortest Path Discovery in the Multi-layered Social Network. ASONAM (p./pp. 497-501), : IEEE Computer Society.</ref>
 ====Burst detection====
 <ref name="Multidimensional Human Dynamics in Mobile Phone Communications">{{Cite doi|10.1371/journal.pone.0103183}}</ref>
+====Path Dominance====
+====Multidimensional betweenness centrality====
 ==Applications==
 Multidimensional network analysis has a wide range of applications.