A study on community detection in multilayer networks

Abstract

Studying complex networks is essential for a better understanding of network science. Many studies have been done on single-layer networks in complex networks. After the advancement and widespread usage of the internet and social media networks, performing community detection in multilayer networks becomes essential to reach more people and work with different personalities on different platforms. Motivated by this observation, this paper has studied types of networks, metrics, measures, and community detection using deep learning-based models in multilayer networks. This survey can play a significant role in analyzing and understanding multilayer networks.

Keywords

Community detection multilayer networks degree modularity social networks

1. Introduction

For two decades, complex networks have become an essential concept in network science. Complex networks have been investigated in many systems such as power grids, the world wide web, biological networks, genetic networks, and social networks [4]. Social networks such as Facebook, Twitter, Linked In, We chat emerged as the best platforms for interaction between different people. Research topics like influence maximization, community detection, and link prediction play a crucial role in social networks. Traditionally complex networks are modeled as single-layer networks, in which nodes and edges are the same behavior and characteristics. However, many natural systems do not support single-layer networks ex: C.elegans nematode. Using the multiple-layer concept, we may overcome this kind of problem. Each person might have accounts and friendship links on different platforms, where friendship links in each platform are treated as a separate layer.

So far, research and literature study of complex networks performed in single-layer networks, where the users (nodes) and interactions (edges) are assumed to belong to the same network. Neglecting some relationships in complex networks may not capture the complete real-time world systems, leading to the complex networks’ incorrect dynamic properties. So, in very recent years, we are witnessing an unprecedented change in the study of complex networks, where interacting nodes belong to different platforms, i.e., layers, this kind of networks called multislice [29], multiplex [12], multilevel [40] and general multilayer networks [19]. A variety of real-world networks have interconnections with different kinds of interactions, ex: Users can have different types of social relationships such as kinship, friendship, and vicinity ship same cultural society forms multilayer public social networks.

Research in multilayer networks is at the infant stage. Minimal data available, the study of multilayer networks interconnects with different topics in social network analysis, including dynamics of networks, link prediction, influence maximization, measures, and metrics of networks, to quantify the behavior of animals. It is related to eco-evolutionary dynamics as connected layers of interactions [17] to model the transportation system. Therefore it is essential to investigate multilayer networks in large-scale complex networks under big global data. As a result, we aim to present a clear picture of multilayer networks.

In recent years, different kinds of measures and metrics have been defined differently from the perspective of multilayer networks. These measures and metrics, such as degree centrality, node overlapping, edge overlapping, page rank centrality, clustering coefficient, and eigenvector centrality, have been extended to identify communities, influential nodes, and link prediction in multilayer networks. For a long time, not only have sociologists realized that it is essential to study the social relation set of nodes based on relation type, but anthologists researchers also proved the importance of diverse social network relation types [41]. So community detection in multilayer networks has also become an important topic in discussions. Similarly, spreading the data in different networks through overlapping nodes in the different layers using information diffusion models also sparked many researchers. We need synthetic networks and real-time data sets to run the implemented algorithms. Many synthetic network packages have been implemented in multilayer networks. We discussed some of them as well as some real-time data sets.

The dynamics of the spreading process in multilayer networks are influenced by many properties like interconnected networks and multiplex networks [33]. The spreading process of interconnected networks studies the impact of inter-layer patterns and interaction strength between layers. Interaction strength between layers depends on some measures; they are the second nearest neighbor, interconnection topology measure, and inter-layer link density. The impact of the inter-layer pattern (i.e., how nodes are connected in different layers) in interconnected network measures based on inter clustering coefficient and inter-degree-degree correlation. Various topics on the spreading process have been discussed recently in multiplex networks. Intra-layer structure, layer similarity, partially interconnected multiplex networks, layer switching cost, are discussed. The properties of the spreading process are discussed, the role of network structure and spreading velocity, interacting spreading process, diffusion of innovations, and resource constraints. Jiexin et al [42] presents the traffic dynamics on multilayer networks. Authors in [42] explains performance indicators such as network capacity, average transmission time etc. They also discusses optimization strategies for improving transmission performance. Walter et al. [14] propose multilayer quality and grade of service support for high speed networks. It proposes a framework for multilayer QoS and GoS support in GMPLS based IP/WDM networks.

Community detection in multilayer networks is one of the research areas with increasing practical significance. Lancichinetti et al. [22] proposed two problems. One is hierarchical community structure; large communities are composed of small communities. The second is overlapping communities when a node is in more than one community like family, friends, professional, etc. Above mentioned traditional communities are applied to small networks and in simple cases. However, real-world networks make traditional methods less applicable in complex and multilayer networks. The deep learning techniques offer optimistic solutions in community detection in multilayer networks. Therefore community detection using deep learning techniques is a new trend, especially in multilayer networks.

To the best of our knowledge, this is the first attempt to study Community detection, including deep learning techniques in multilayer networks. The significant contribution of the proposed work is given as follows.

We have done a study on various networks models of multilayer networks.

We provide a detailed study of measures and metrics used in multilayer networks.

We provide a brief study of community detection, including deep learning techniques in multilayer networks.

Applications of multilayer networks introduced and as well as future scope of the multilayer networks.

This section provides a detailed introduction of multilayer networks, the rest of the paper organized in the following way. In Section 2, we discussed the network model, i.e., multilayer networks and multiplex networks. Section 3 presents metrics and measures of multilayer networks and aggregating the many networks into a single network, i.e., coupling networks. Section 4 briefed on dynamics of multilayer networks; it consists of a broad range of research in the domain of community detection. In Section 5, we presented the applications of the multilayer networks. Finally, Section 6 presents about Conclusion and Future Work.

2. Network model

The Graph consists of many networks, and each network treats as a layer. Many authors proposed many network models for the definition of multilayer networks. We discussed two main models as multiplex networks and multilayer network models. Most of the authors aggregate all the layers in a multilayer network into a single network. Given a Multilayer Graph $G = (V_{L}, E_{L}, V_{M}, M)$ be a multiplex network. In Fig. 1, we presented the multilayer networks and multiplex networks.

2.1. Multiplex network

Multiplex is a particular type of multilayer network. Each layer has an exact number of nodes in a multiplex network, and possible interlayer connections exist between replica nodes. Intralayer connections can exists between any of two nodes in the same layer. Representation of M-layer Multiplex network is $M = {G^{1}, \dots, G^{α}, \dots, G^{M}}$ , where $α^{t h}$ layer in multiplex network is $G^{α} = {V^{α}, E^{α}}$ and $V^{α}$ , $E^{α}$ is set of nodes and set of edges in layer α. The single layer network with N number of nodes and M number of edges can be represented with $N * N$ size matrix called Adjacency matrix, whose entry $a_{i j}$ is 1 means link existed between i and j, $a_{i j}$ is 0 means no link exists between i and j. But in multiplex network, we need supra adjacency matrix required i.e $N M * N M$ [15], N is number of nodes in each layer and M is number of layers in network. $\begin{matrix} A = (\begin{matrix} A^{(1)} & I_{N} & - & - & I_{N} \\ I_{N} & A^{(2)} & - & - & I_{N} \\ - & - & - & - & - \\ - & - & - & - & - \\ I_{N} & I_{N} & - & - & A^{(M)} \end{matrix}) \end{matrix}$ where $I_{N}$ is identity matrix with $N * N$ .

Random walks are an easy way to explore the multiplex networks [7]. Different kind of biased random walks has been studied. Degree-biased random walks are used in many cases like finding centrality measures, community detection, influence maximization algorithms. Since many interconnected layers require many biased random walks, mainly divided into intensive and extensive walks.

Fig. 1.

(A) Multiplex network. (B) Multilayer network.

2.2. Multilayer network

A multilayer network model is intra and interconnected graph network $M = (V^{M}, E^{M}, V, L)$ , where $V^{M} \subseteq V \times L^{1} \times L^{2} \times \dots \times L^{m}$ is the set of node layer combinations, $E^{M} \subseteq V^{M} \times V^{M}$ is the edge set in multilayer network containing the possible pair of combinations and elementary layers, V is set of nodes in multilayer network and $L = {L^{α}}_{α = 1}^{m}$ , $α ⩾ 2$ . Nodes need not be homogeneous, and a node u can exist in many layers [18].

In a multilayer network, each layer may not have the same number of nodes; nodes also may be different. In general a node u in layer X can be connected to node v in any layer Y [1]. Layers will represent the node’s character, behavior, and aspect and links in that layer.

If $A_{i j}^{X Y}$ is 1 means link exists between node i in layer X and j in layer Y, $A_{i j}^{X Y}$ is 0 means link does not exist between i in layer X and j in layer Y.

Given a graph $G = (V, E)$ and also represented as $G = {G^{1}, G^{2}, \dots, G^{m}}$ , $L^{i} = {V^{i}, E}$ , $V^{i} = {v_{1}^{i}, \dots, v_{n}^{i}}$ is a multilayer network [8]. $| V | = m * n$ , where m is number of layers in a multilayer network and n is number of nodes in each layer. $\begin{matrix} A = (\begin{matrix} A^{(1)} & A^{(12)} & - & - & A^{(1 P)} \\ A^{(21)} & A^{(2)} & - & - & A^{(2 P)} \\ - & - & - & - & - \\ - & - & - & - & - \\ A^{(P 1)} & A^{(P 2)} & - & - & A^{(P)} \end{matrix}) \end{matrix}$

Any two nodes can be connected in the network, i.e., nodes in the same layer or nodes in different layers. Most of the study has been performed in multiplex networks, and study in multilayer networks is minimal because most of the reference papers are in multiplex networks.

3. Metrics and measures of multilayer networks

Traditional measures and metrics in a single layer are also defined in multilayer networks, but some metrics are defined differently in multilayer networks. This section discuss the different metrics in multiplex networks, including edge overlap, clustering coefficient, degree centrality, page rank centrality, eigenvector centrality.

Battiston et al. [6], introduced basic metrics are, i.e., node overlap and edge overlap in the multiplex network. Edge overlap is defined as there exists an edge between two nodes in the same layer occurs in different layers, then edge overlap of an edge $i - j$ between two layers is $\begin{matrix} (1) & o_{i j}^{[α, α^{‘}]} = b_{i j}^{[α]} + b_{i j}^{[α^{‘}]} \end{matrix}$ The edge overlap of two nodes i and j, $o_{i j}$ is $\begin{matrix} (2) & o_{i j} = \sum_{α} b_{i j}^{[α]} \end{matrix}$

Where $b_{i j}^{[α]}$ is 1, if there exists edge between i and j in layer α.

Node i of the degree in layer α is $k_{i}^{[α]} = \sum_{j} b_{i j}^{[α]}$ and total degree of the same node in all the layers is $k_{i} = k_{i}^{[1]} + k_{i}^{[2]} +, \dots . + k_{i}^{[M]}$ . Based on edge overlap, we can also identify node overlap $\begin{matrix} (3) & o_{i} = \sum_{j} o_{i j} = \sum_{α} k_{i}^{[α]} \end{matrix}$

The clustering coefficient in a monoplex network is the ratio of the number of links between the neighbors of a node to the maximum possible number of links between neighbors. $CC (i) =$ Number of links between neighbours of node i / Maximum possibility of number of links between neighbours of i.

Degree centrality is a measure to identify the neighbors of a node v, degree centrality (DC) of node v is $\begin{matrix} (4) & DC (v) = degree (v) \end{matrix}$

Degree centrality of a node $i$ in multiplex network is a vector, degree centrality of node $i$ in multiplex network ${DC}_{i}$ is $\begin{matrix} (5) & {DC}_{i} = {{DC}_{i}^{1}, {DC}_{i}^{2}, \dots, {DC}_{i}^{M}} \end{matrix}$

Singular Vector of Tensor (SVT) centrality [38] used to quantitatively find the importance of nodes connected by different kind of connections in multilayer networks. $\begin{matrix} (6) & V_{i} = \frac{1}{L} \sum_{α = 1}^{L} V_{i}^{α} (1 ⩽ i ⩽ N) \end{matrix}$ where $V_{i}^{α} = V^{(1)} (i) \cdot V^{(2)} (α) + V^{(3)} (i) \cdot V^{(4)} (α)$ , $[1 ⩽ i ⩽ N; 1 ⩽ α ⩽ L]$ the singular vector tensor centrality of node $i$ in layer α.

Page rank centrality [37] is a measure to give ranking to the nodes based on incoming edges to particular node. Page rank $S_{i}^{(L)} (t)$ is for node $i$ in layer L at time step $t$ . $\begin{matrix} (7) & S_{i} (t + 1) = \sum_{L} \sum_{j} g_{j i}^{(L)} \frac{α_{L} S_{i} (t)}{H_{j}^{(L)}} + (1 - \sum_{L} α_{L}) V_{i} \end{matrix}$ where $H_{j}^{(L)} = \sum_{r} g_{j r}^{(L)} + δ (0, \sum_{r} g_{j r}^{(L)})$ , $α_{L} = [0, 1), δ (a, b)$ is kronecker delta, which equals 0 if $a \neq b$ and 1 if $a = b$ , $g_{j i}^{(L)}, L = {1, 2, \dots, M}$ , if $g_{j i}^{(L)}$ is 1 means link exists between j to i in layer L, 0 means no link exists between j to i in layer L.

In a single-layer network, the eigenvector centrality of node i is defined as the $i^{t} h$ component of the eigenvector associated with the eigenvalue of the leading adjacency matrix of the network. For multilayer, we can evaluate the eigenvector centrality of a node at each layer. Eigen vector centrality [6] of a node i in multilayer network is a vector: $\begin{matrix} (8) & E_{i} = {E_{i}^{[1]}, E_{i}^{[2]}, E_{i}^{[3]} \dots E_{i}^{[M]}} \end{matrix}$ $E_{i}^{l}$ is eigen vector centrality of a node i in layer l.

To measure the impact of layers interrelation on information spreading process in between two layers correlation coefficient (CrC) [43] can be used, the CrC for two layer network is: $\begin{matrix} (9) & CrC (G) = \frac{\sum (k_{A, i} - \overline{k_{A}}) (k_{B, i} - \overline{k_{B}})}{\sqrt{\sum {(k_{A, i} - \overline{k_{A}})}^{2}} \sqrt{\sum {(k_{B, i} - \overline{k_{B}})}^{2}}} \end{matrix}$

$k_{A, i}$ represents degree of node $i$ in layer A, $\overline{k_{A}}$ represents average degree of layer A. Similarly $k_{B, i}$ represents degree of node i in layer B, $\overline{K_{B}}$ represents average degree of layer B.

Pearson correlation coefficient (PCC) [28] is a measure to find the linear correlation between two nodes. PCC is used to find overlap between three layers estimated from pairwise PCC in multilayer networks. Pearson correlation coefficient i.e ${PCC}_{p, k, l}$ $\begin{matrix} (10) & {PCC}_{p, k, l} = \frac{\sum_{i > j} (w_{i j}^{L_{k}} - w^{L_{k}}) (w_{i j}^{L_{l}} - w^{L_{l}})}{\sqrt{\sum_{i > j} (w_{i j}^{L_{k}} - w^{L_{k}})} \sqrt{\sum_{i > j} (w_{i j}^{L_{k}} - w^{L_{k}})}} \end{matrix}$

$w_{i j}^{L_{k}}$ represents link weight between node i and j in layer k. $w^{L_{k}}$ is the average of all the link weights in layer k.

Cross-layer degree centrality (CLDC) [10] is defined as the sum of cross-layer in-degree centrality and cross-layer out-degree centrality. $\begin{matrix} (11) & CDLC (a, α) = {CLDC}^{In} (a, α) + {CLDC}^{Out} (a, α) \end{matrix}$

Whereas cross-layer in-degree centrality is the ratio between the sum of the edge weights incoming to node a towards multilayer neighborhood $M u N (a, α)$ and number of layers X total number of network numbers. $\begin{matrix} (12) & {CLDC}^{In} (a, α) = \frac{\sum_{b \in M u N (a, α)} weight (b, a, l)}{(m - 1) | L |} \end{matrix}$

Whereas cross-layer out-degree centrality is the ratio between the sum of the edge weights that are outgoing from node b towards multilayer neighborhood $M u N (b, α)$ and the layer of layers X total number of network numbers. $\begin{matrix} (13) & {CLDC}^{Out} (a, α) = \frac{\sum_{y \in M u N (a, α)} weight (a, b, l)}{(m - 1) | L |} \end{matrix}$

Here $weight (a, b, l)$ is weight of edge between node a and b in layer l, $weight (b, a, l)$ is weight of edge between node b and a in layer l and $M u N (a, α)$ is multilayered neighbourhood for a node a, is a set of nodes which are directly connected to a in at least l layers.

3.1. Coupling of the networks

Interlayer connections between replica nodes in multilayer networks happen through coupling; Murata et al. [31] discussed two types of couplings, i.e., ordinal and categorical. In ordinal coupling, the inter-layer edges exist only between replica nodes adjacent layers. In categorical coupling, the inter-layer edges exist between replica nodes in all the layers.

Coupling the nodes in the network happens via lossy or lossless coupling schemes [44]. In a lossless coupling scheme, the resultant network will maintain all the features and quality of the original network without any loss. The lossy coupling scheme offers an alternative solution that may compromise quality, and the resultant network may also lose some features. Generally, lossy coupling uses when memory and time constraints exist. Different lossless coupling schemes use to couple the multiplex into a single layer network; they are clique lossless coupling scheme, star lossless coupling scheme, reduced lossless schemes, and extension to another diffusion model.

4. Community detection in multilayer networks

Complex networks are inherently organized as communities, i.e., clusters or modules with sparse external links and dense internal links. Since communities have common properties, community structure helps better understand and overall function of the network. Community detection has been studied extensively in single-layer networks for many decades. Researchers are working on community detection in multilayer networks (MLCD). Practical approaches for finding MLCD can be divided into three main categories, first is direct methods, second is flattening methods, and third is aggregating methods [35]. Indirect methods directly identify the multilayer networks as inputs by optimizing some multilayer quality assessment criteria. In flattening methods, the single-layer will be detected on multilayer networks; after the detection of single layer network, apply conventional community algorithm to detect communities. In aggregation methods, community structure identifies on each network layer separately; after that aggregation, the mechanism will be used to identify the final community structure.

Xing Su et al. [34] proposed five deep learning categories for community detection. They are Conventional networks, Generative Adversarial Network (GAN), Graph Attenuation Network (GAtN), Deep Sparse filtering, Auto Encoder. GAtN is crucial at special attention to community signals. The conventional network consists of conventional neural networks and graph conventional networks (GCN). Auto encoder has subcategories; it consists of noise auto encoder, graph attention auto encoder, and variational auto encoder.

Cao et al. [11] proposed deep neural networks for graph representation (DNGR), it applies denoise encoder to increase the robustness for capturing structural data when detecting communities in multilayer network. Li et al. [23] proposed clustering oriented network using deep networks and it is extension to DNGR to connect the cluster assignments. Mehta et al. [27] proposed overlap stochastic block model is a fast recognition model that enables the fast inference of the node to detect the communities across the network.

Researchers use modularity measures to find the strength of community; the modularity concept uses for several optimization methods to discover communities in the network, including spectral division, external optimization, greedy agglomeration, and simulated annealing. Ma et al. [26] proposed a new algorithm semi-supervised joint non-negative matrix factorization (S2-JNMF) to find communities in multi-layer networks. S2-JNMF consists of three stages, one is priori information construction, the second is non-negative matrix factorization, and the third is community detection. Priori information has two steps; in the first step, the greedy step strategy has been used to identify dense subgraphs in a multi-layer network. In the second step, the strategy starts at one node called seed node, and it keeps expanding the subgraph until it finds the density of the subgraph in some layers of the multi-layer network is less than the predefined threshold. In non-negative matrix factorization, based on subgraph, construct the semi-supervised matrix. In community detection, obtain the community using a matrix. The time complexity of the algorithm is $O (r n^{2} k m)$ , where r is the number of iterations, k is a number of communities, m is a number of layers, and n is a number of nodes in the graph G.

Pramanik et al. [32] proposed new modularity index called multilayer modularity index ( $Q_{M}$ ). Implemented Girvan newman and Louvain algorithms to multilayer networks by modifying the same algorithms in single layer networks using multilayer modularity index $Q_{M}$ . Multilayer modularity index ( $Q_{M}$ ) is $\begin{array}{rcl} Q_{M} & = & \frac{1}{3} \sum_{k = 1}^{n_{c}} [\forall_{i}, J \in C_{k} {\frac{1}{2 | E_{1} | + θ_{C_{k}} * | E_{12} |} \\ \times \sum_{i, j \in V_{1}} (A_{i} j - \frac{h_{i} + θ_{C_{k}} * C_{i}) * (h_{j} + θ_{C_{k}} * C_{j})}{2 | E_{1} | + θ_{C_{k}} * | E_{12} |}) + \frac{1}{2 | E_{1} | + 2 | E_{2} | + | E_{12} |} \\ \times \sum_{i \in V_{1}, j \in V_{2}} (A_{i j} - \frac{(C_{i}^{‘} + C_{j}^{‘})}{2 | E_{1} | + 2 | E_{2} | + | E_{1} 2 |}) + \frac{1}{2 | E_{2} | + θ_{C_{k}} * | E_{12} |} \\ \times \sum_{i, j \in V_{2}} (\frac{A_{i j} - (h_{i} + θ_{c_{k}} * c_{i}) * (h_{j} + θ_{c_{k}} * c_{j})}{2 | E_{2} | + θ_{C_{k}} * | E_{12} |})}] \end{array}$

$θ_{c_{k}}$ is type of community, if $θ_{c_{k}}$ is 1, then $c_{k}$ is single layer community, $θ_{c_{k}}$ is 0, then $c_{k}$ is cross layer community. $n_{c}$ is total number of apriori communities. Instead of Grivan-new modularity index, they applied multilayer modularity index( $Q_{m}$ ) and implemented GN- $Q_{M}$ algorithm, similarly instead of lovian modularity they applies multilayer modularity index and implemented lovian- $Q_{M}$ algorithm.

With the complexity of multi-layer networks, it has become more complicated to get the actual data of the network. Even though we get the global structured data, computation task might be much high, it may not be possible in real-time networks, so to overcome this problem, XiaoMingLi et al. [25] proposed a new community detection algorithm called multi-layer social network based on a local random walk (MRLCD), it has two stages one finds the core node, core node determines based on repeatability of the node in the multi-layer network. The second is the core clustering stage based on a local random walk. In the random walk, find the scope of the node based on intra and interlayers trust.

Interdonato et al. [18] proposed local community detection in multi layer networks(ML-LCD) method takes multilayer network and seed node v as input. It computes the local community C is associated to v. Different measures have been used to compare the results in ML-LCD are ML-LCD-lw on layer weighting, ML-LCD-wlsim on with in layer similarity and ML-LCD-clsim on cross layer similarity, Ml-LCD-lw and ML-LCD-wlsim is $\begin{array}{l} L C_{v}^{int} = | C | L C^{int} + \sum_{u \in C} \sum_{L_{i} \in L \land (u, v) \in E_{i}^{C}} ω_{i} \\ L C_{V}^{ext} = | B | L C^{ext} + \sum_{u \in S_{v}} \sum_{L_{i} \in L \land ((u, L_{i}), (v, L_{i})) \in E_{L}} ω_{i} - \sum_{u \in B_{v}} \sum_{L_{i} \in L \land (u, v) \in E_{i}^{B}} ω_{i} \end{array}$

ML-LCD-clism is $\begin{array}{l} L C_{v}^{int} = | C | L C^{int} + \sum_{u \in C} \sum_{L_{i}, L_{j} \in L \land ((u L_{i}), (v, L_{j})) \in E_{L}} {sim}_{i, j} (u, v) \\ (14) & L C_{V}^{ext} = | B | L C^{ext} + \sum_{u \in S_{v}} \sum_{s \in S} \sum_{L_{i}, L_{j} \in L \land ((u, i), (s, j)) \in E_{L}} {sim}_{i, j} (u, s) \\ - \sum_{u \in B_{v}} \sum_{s \in S} \sum_{L_{i}, L_{j} \in L \land ((u, i), (s, j)) \in E_{L}} {sim}_{i, j} (u, s) \end{array}$ Computational complexity is $O (| C |^{2} * k * Φ)$ where k is the maximum degree of a node in the network, Φ is the computational cost of local community functions and C is the size of community

Brodka et al. [9] proposed a new measure called cross-layer edge clustering coefficient (CLECC), which was developed based on the idea of edge clustering coefficient. Calculate CLECC for all the possible pairs of x, y in layer α. Then remove all low coefficient edges and recalculate them. The process repeats until subgraphs or isolated nodes occur. Subgraphs are communities in a multilayer network. $\begin{matrix} CLECC (x, y, α) = \frac{| M N (x, α) \cap M N (y, α) |}{| M N (x, α) \cup M N (y, α) / {x, y} |} \end{matrix}$ where $M N (x, α)$ is neighbourhood list of node x in layer α. It represented as $\begin{matrix} M N (x, α) = {y : | {l : ⟨ x, y, l ⟩ \in E \lor ⟨ y, x, l ⟩ \in E} | ⩾ α} \end{matrix}$

Kuncheva et al. [21] proposed an algorithm locally adaptive random transitions (LART) to find communities in the multiplex network, the algorithm based on the random walk in multiplex and transition probabilities. The random walk will perform within and across in multilayer networks; a node $v_{i}^{m}$ can perform four possible moves, i.e., when it stays in $L^{m}$ , it can stay at the same place $v_{i}^{m}$ , or it can move to any neighbor $v_{j}^{m}$ in the same layer $L^{m}$ ; or if it moves to another layer $L^{n}$ , then it can stays at $v_{i}^{n}$ or it can move to another node $v_{j}^{n}$ in layer $L^{n}$ . For each move, corresponding transition probabilities will be associated. These transition probabilities depend on the local topological similarity between any pair of nodes; in order to cluster the nodes, dissimilarity measure between nodes used to capture the community structure in the multiplex.

Tang et al. [36] discussed to extracting structural features from each dimension of networks using modular analysis, then integrate all of them to find out community structure. Three kind of modularity analysis concepts has been discussed i.e. Average modularity maximization, total modularity maximization and principal modularity maximization. In average modualrity maximization, treat M-layer as 1- layer by aggregating the network and Average maximize modularity is $\begin{matrix} max Q = \frac{1}{2 \overline{m}} T_{r} (S^{T} [\overline{A} - \frac{\overline{d} \overline{d^{T}}}{2 \overline{m}}] S) \end{matrix}$ where as $\overline{A}$ is average interaction network among social actors $\overline{A} = \frac{1}{d} \sum_{i = 1}^{d} A_{i}$ and $\overline{m} = \frac{1}{d} \sum_{i = 1}^{d} m_{i}$ and $\overline{d} = \frac{1}{d} \sum_{i = 1}^{d} d_{i}$ .

In total modularity maximization maximizes the total modularity in all the layers, it considers degree distribution in each dimension is different where as in AMM degree distribution is same. Total maximization modularity is $\begin{array}{rcl} max Q & = & \frac{1}{d} \sum_{i = 1}^{d} Q_{i} = \frac{1}{d} \sum_{i = 1}^{d} T_{r} (S^{T} \frac{B}{2 m_{i}} S) \\ = & T_{r} (S^{T} [\frac{1}{d} \sum_{i = 1}^{d} {\frac{A}{2 n_{i}} - \frac{d d^{T}}{{(2 m_{i})}^{2}}}]) \end{array}$

Where $Q_{i}$ modulairty of ith dimension. $S \in {0, 1}^{n * k}$ be c community indication matrix; $S_{i j}$ is 1 if i and j are in same community else it is 0.

In AMM and TMM, different dimensions have been aggregated into single-layer networks. However, in PMM, extract the structural features at each dimension then perform cross dimensional integration. Principal modularity maximization consists of two steps, one is structural feature extraction, and the second is cross-dimension integration. In structural feature extraction, extract the features from each dimension via modularity maximization; Then apply the principal component analysis (PCA) on the concatenated data to identify top eigenvectors as modularity matrix. After projecting the data onto the principal vectors, Compute low dimensional embedding with the help of the top eigenvector of modularity matrix and then perform k-means on the low embedding to find the possible communities. As part of the comparison, they compared AMM, TMM, and PMM with single-layer modular maximization. Performance seems to be like $AMM < T M M < PMM$ .

Amelio et al. [3] proposed a new method multilayer genetic algorithm(MultiGA) to detect the community structure in multilayer networks. MultiGA adopts the genetic representations of individuals that allow cooperation and co-evolution among all the network layers. Each individual has n genes, after decoding the genes, evaluate community structures(CS). After identifying community structures, A new modularity concept has been introduced for evaluating fitness function by combining modularity values computed for each layer. Let a and b are layers of multilayer network, ${CS}_{a}$ and ${CS}_{b}$ are the community structures obtained from the Layer $L_{a}$ and $L_{b}$ respectively, Then combined modularity $Q_{a b}$ between layers a and b is as follows $\begin{matrix} Q_{a b} = \frac{1}{2 (m_{a} + m_{b})} \sum_{i j} [(A_{i j a} - \frac{d_{i a} d_{j a}}{2 m_{a}}) Δ (C_{i a}, C_{j a}) + (A_{i j b} - \frac{d_{i b} d_{j b}}{2 m_{b}}) Δ (C_{i a}, C_{j a})] \end{matrix}$

Where $A_{a}$ and $A_{b}$ are the adjacency matrix of network layer a and b respectively and $d_{i a}$ and $d_{j a}$ are the degree of node i and j in layer $L_{a}$ , The Kronecker function Δ is 1, if i and j are same community $C_{s}$ , otherwise 0.

Similarly combined modularity of $Q_{b a}$ between layer b and a is as follows $\begin{matrix} Q_{b a} = \frac{1}{2 (m_{b} + m_{a})} \sum_{i j} [(A_{i j b} - \frac{d_{i b} d_{j a}}{2 m_{b}}) Δ (C_{i b}, C_{j b}) + (A_{i j a} - \frac{d_{i a} d_{j a}}{2 m_{a}}) Δ (C_{i b}, C_{j b})] \end{matrix}$

The total combined modularity of $Q_{m l}$ is computed on the all the layers by considering the sum of combined modularities on $Q_{a b}$ for each couple of slices, $Q_{m l}$ is $\begin{matrix} Q_{m l} = \sum_{a, b a \neq b} (Q_{a b} + Q_{b a}) \end{matrix}$

Mucha et al. [30] proposed multislice modularity for knowing the fitness of communities in multilayer networks. For quantifying communities in multilayer networks, quality functions have been used; quality function compares the number of intracommunity edge weight minus expected at random fails to provide any contribution from the interlayer coupling. Based on quality functions, multislice generalization of modularity has generated, $Q_{m s} L$ $\begin{array}{rcl} Q_{m s} (L) & = & \frac{1}{k (V_{L})} \sum_{u, v, L_{i} . L_{j}} [(A_{u v L_{i}} - Γ_{i} \frac{k_{L_{i}} (u) k_{L_{i}} (v)}{2 | E_{i} |}) \\ (15) & * Γ_{L_{i}, L_{j}} + Γ_{u . v} C_{v, L_{i}, L_{j}}] Γ (g_{u}, L_{i}, g_{v}, L_{j}) \end{array}$

Where $k (V_{L})$ is total degree of multilayer network graph G, $k_{L_{i}} (v)$ is degree of node v in layer $L_{i}$ . $A_{u v L_{i}}$ represents the edge between u and v in layer $L_{i}$ . $Γ_{i}$ is resolution parameter of layer $L_{i}$ . $C_{v, L_{i}, L_{j}}$ represents the edges of node v in layer $L_{i}$ and $L_{j}$ . $Γ_{L_{i}, L_{j}}$ is equal to 1, if $L_{i}$ and $L_{j}$ are same, otherwise it is 0. $Γ_{u, v}$ is 1 if u and v are same else it is 0.

In the above $Q_{m s}$ , i.e., multislice modularity, there is no specification of a way to set layer weighting scheme. It also did not discuss inter-layer coupling or any layer comparability constraints. To overcome the issues, one definition has been introduced modularity of multilayer networks by Amelio et al. [2]; it focused on two key elements in multilayer modularity, i.e., layer-specific resolution and interlayer coupling. $\begin{matrix} Q_{C} = \frac{1}{d (V_{L})} \sum_{c \in C} [\sum_{l \in L} (d_{l}^{int} (c) - Γ (l, c) \frac{{(d_{l} (c))}^{2}}{d (V_{L})} + β \sum_{l_{1} \in p (l)} I C (c, l, l_{1}))] \end{matrix}$

Where $l \in L$ , community structure $C = {c_{1}, c_{2}, \dots c_{k}}$ as a partitioning of multilayer graph G. $d_{l}^{int} (c)$ and $d_{l} (c)$ is internal degree of community c and degree of community c in layer l, by considering only edges of layer l.

$Γ (l, c)$ is the value of the resolution function, $I C (c, l, l_{1})$ is interlayer coupling for any valid layer l, $β \in {0, 1}$ is a parameter to control the inclusion or exclusion of inter layer coupling.

Jianxin et al. [24] proposed community diversified influence maximization (CDIM) to address the computational complexity in previous models. It uses the CPSP-tree index to find k influential users in the social network. Yuqing et al. [45] propose influential pricing nodes in the networks based on their expected influence spread. Authors in [45] design a function to characterize the relationship between price and expected influence.

Kumar et al. [13] propose IM using Extended h-index and Label Propagation with Relationship matrix (IM-ELPR). IM-EPLR has four phases, first is the seeding phase to select the candidate seed nodes, second is the label propagation phase to find the communities with the help of seed nodes. The third phase is to merge the communities using a relationship matrix, and the fourth phase is to select the k influential nodes using the rank measure. Xuanhao et al. [15] propose community-based influence maximization in Location-based social networks (LBSN), which comprises three steps. First step is to find the communities based on Spatio-temporal similarity measures between users. The second step finds the candidate nodes using the candidate selection algorithm. In the third step, it uses two community detection algorithms to find final seed nodes. Table 1 explains the different community detection methods and its functionalities.

Table 1
Community detection algorithms in multilayer networks

Network model Major finding Time complexity Dataset

S2-JNMF Multilayer network Identifying communities $O (r n^{2} k m)$ Semi synthetic dataset

GN- $Q_{M}$ Lovian $Q_{M}$ Multiplex Finding seed nodes $O ((k + l) (m + n) log \frac{n}{e^{2}} + (k l))$ Twitter, FSQ and Synthetic network

MRLCD Boolean multilayer network Finding communities O(MNlogN) AARHUS, EU-AIR, MIT Media club

MultiGA Multiplex Identifying key nodes in biological networks N YLMN, H3N2 HIMN and LCMN

ML-LCD Multilayer network Identifying seed nodes $(1 - 1 / e)$ AUCS, Biogrid and DBLP

CLECC N Y N Y

EMCD Y Aggregation Y Twitter, FSQ

M-EMCD Multiplex Identifying communities NA FF-TW-YT

LART N Finding communities NA Synthesis Network

AMM, TMM, PMM Multiplex Aggregation NA YT API Data, Synthetic Data

	Network model	Major finding	Time complexity	Dataset
S2-JNMF	Multilayer network	Identifying communities	$O (r n^{2} k m)$	Semi synthetic dataset
GN- $Q_{M}$ Lovian $Q_{M}$	Multiplex	Finding seed nodes	$O ((k + l) (m + n) log \frac{n}{e^{2}} + (k l))$	Twitter, FSQ and Synthetic network
MRLCD	Boolean multilayer network	Finding communities	O(MNlogN)	AARHUS, EU-AIR, MIT Media club
MultiGA	Multiplex	Identifying key nodes in biological networks	N	YLMN, H3N2 HIMN and LCMN
ML-LCD	Multilayer network	Identifying seed nodes	$(1 - 1 / e)$	AUCS, Biogrid and DBLP
CLECC	N	Y	N	Y
EMCD	Y	Aggregation	Y	Twitter, FSQ
M-EMCD	Multiplex	Identifying communities	NA	FF-TW-YT
LART	N	Finding communities	NA	Synthesis Network
AMM, TMM, PMM	Multiplex	Aggregation	NA	YT API Data, Synthetic Data

5. Multilayer network applications

In this section we discussed some applications of multilayer networks. we did not cover subject applications detail, but we kept more references, interested readers can go through easily [1].

5.1. Transportation system

There are many datasets on multiplex networks like EU air transport, London metro system or Six Continental airlines, etc. There can be several ways of transport mode like bus, rail or air, etc. Any of the transport modes can be used between any two locations, transport services follow different routes, stations/ locations are the nodes, and paths they follow are edges of the network. Alessio Cardillo et al. [13] studied the dynamics of the European air transport network, where each airline is a layer and airports are nodes of the multilayer network.

5.2. Multilayer networks in social networks

Multilayer networks in sociology uses in many places like marketing, product advertisements, virus spreading using Information diffusion models after finding influential nodes in different networks [5,16,20,39] and to find similar kind of people in networks [3,21,26,32]. Other than this, we can also use to find the future friendship links in different networks with help of prediction algorithms. We also discusses the biological networks here. Studying the biological elements and their interactions are crucial for knowing about biomolecules and biological process. Research in biological networks aims to organize the biological structures to desired states by manipulating signals. Zheng et al. [27] has proposed a framework for controlling nonlinear dynamical systems with the dynamic approach in multilayer networks and applied target identification of diseases. Similarly, some other applications. Shinde et al. [24] studied protein to protein interaction analysis in multilayer network analysis of different life stages in Caenorhabditis elegans, where each layer represents a life stage of bacteria. Zitnik et al. [45] discussed the prediction of multi cellular function through multilayer tissue network.

6. Conclusion and future work

This study provides a comprehensive overview of the state of the art measures, metrics and community detection in multilayer networks. In the last decade, most of the community detection studies done on single layer network. According to our study, these methods are efficient, effective and applicability of community detection in multilayer networks. As communities have more edge denisity, nodes in communites do have frequent interaction with other nodes in the community. This property will helps in increase in the information spread in the community as well as network. Therefore, community based models can give better performance than traditional algorithms.

In the future, we will explore influence maximization, community detection and link prediction in multilayer networks using different domains such as game theory, recommender systems, etc. To the best of our knowledge, few researchers works on influence maximization using community structures in multilayer networks.

Conflict of interest

None to report.

References

Aleta and

Moreno , Multilayer Networks in a Nutshell, arXiv:1804.03488 [physics.soc-ph].

Amelio ,

Mangioni and

Tagarelli , Modularity in multilayer networks using redundancy-based resolution and projection-based inter-layer coupling, IEEE Trans. on Network Science and Engineering (2019). doi:10.1109/TNSE.2019.2913325.

Amelio and

Pizzuti , A cooperative evolutionary approach to learn communities in multilayer networks, in: Proceedings of PSSN, 2014, pp. 222–232.

A.-L.

Barabasi , Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life, Plume Books, 2003.

Basaras ,

Iosifidis ,

Katsaros and

Tassiulas , Identifying influential spreaders in complex multilayer networks: A centrality perspective, in: IEEE Transactions on Network Science and Engineering, Vol. 6, 2019.

Battiston ,

Nicosia and

Latora , Structural measures for multiplex networks, Sigmod Record 42(2) (2013), 17–28.

Battiston ,

Nicosia and

Latora , Efficient exploration of multiplex networks, New J. Phys. 18 (2016), 043035. doi:10.1088/1367-2630/18/4/043035.

Boccaletti ,

Bianconi ,

Criado ,

C.I.

del Genio ,

Gómez-Gardeñes ,

Romance ,

Sendiña-Nada ,

Wangl and

Zanin , The structure and dynamics of multilayer networks, Physics Reports 544 (2014), 1–122.

Bródka ,

Filipowski and

Kazienko , An introduction to community detection in multi-layered social network, in: International Conference on Data Science and Advanced Analytics, 2017.

10.

Bródka ,

Skibicki ,

Kazienko and

Musiał , A degree centrality in multi-layered social network, in: International Conference on Computational Aspects of Social Networks (CASoN), 2011.

11.

Cao ,

Lu and

Xu , Deep neural networks for learning graph representations, in: AAAI, 2016, pp. 1145–1152.

12.

Cardillo ,

Gómez-Gardeñes ,

Zanin ,

Romance ,

Papo ,

del Pozo and

Boccaletti , Emergence of network features from multiplexity, 2013, arXiv:1212.2153 [physics.soc-ph].

13.

Cardillo ,

Zanin ,

Gómez-Gardeñes ,

Romance ,

A.J.

García del Amo and

Boccaletti , Modeling the multi-layer nature of the European air transport network: Resilience and passengers re-scheduling under random failures, The European Physical Journal Special Topics 215 (2013), 23–33. doi:10.1140/epjst/e2013-01712-8.

14.

Colitti ,

Steenhaut ,

Nowé and

Lemeire , Multilayer quality and grade of service support for high speed GMPLS IP/DWDM networks, in: Network-Based Information Systems. NBiS 2007,

Enokido ,

Barolli and

Takizawa , eds, Lecture Notes in Computer Science, Vol. 4658, Springer, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-74573-0_20.

15.

D.R.

DeFord and

S.D.

Pauls , A new framework for dynamical models on multiplex networks, arXiv:1507.00695.

16.

Dimokas ,

Katsaros ,

Tassiulas and

Manolopoulos , High performance, low complexity cooperative caching for wireless sensor networks, in: Wireless Netw, 2007.

17.

K.R.

Finn ,

M.J.

Silk ,

M.A.

Porter and

Pinter-Wollman , The use of multilayer network analysis in animal behaviour, arXiv:1712.01790.

18.

Interdonato ,

Tagarelli ,

Ienco ,

Sallaberry and

Poncelet , Local community detection in multilayer networks, Data Min Knowl Disc 31 (2017), 1444–1479. doi:10.1007/s10618-017-0525-y.

19.

Kivelä ,

Arenas ,

Barthelemy ,

J.P.

Gleeson ,

Moreno and

M.A.

Porter , Multilayer networks, Physics and Society. Journal of Complex Networks 2(3) (2014), 203–271. doi:10.1093/comnet/cnu016.

20.

Kuhnle ,

M.A.

Alim ,

Li ,

Zhang and

M.T.

Thai , Multiplex influence maximization in online social networks with heterogeneous diffusion models, Mathematical Programming 14 (2018).

21.

J.Z.

Kuncheva and

Montana , Community detection in multiplex networks using locally adaptive random walks, 2017, arXiv:1507.01890. doi:10.1098/rsos.160863.

22.

Lancichinetti ,

Fortunato and

Kertész , Detecting the overlapping and hierarchical community structure in complex networks, New J Phys 11(3) (2009), 033015. doi:10.1088/1367-2630/11/3/033015.

23.

Li ,

Pi ,

Lin and

Cui , DNC: A deep neural network-based clustering-oriented network embedding algorithm, Journal of Network and Computer Applications 173 (2021), 102854. doi:10.1016/j.jnca.2020.102854.

24.

Li ,

Cai ,

Deng ,

Wang ,

Sellis and

Xia , Community-diversified influence maximization in social networks, Information Systems 92 (2020), 101522, ISSN 0306-4379, https://www-sciencedirect-com-443.web.bisu.edu.cn/science/article/pii/S0306437920300326. doi:10.1016/j.is.2020.101522.

25.

X.M.

Li ,

Xu and

Tang , Community detection for multi-layer social network based on local random walk, Journal of Visual Communication and Image Representation (2018), 91–98. doi:10.1016/j.jvcir.2018.10.003.

26.

Ma ,

Dong and

Wang , Community detection in multi-layer networks using joint nonnegative matrix factorization, IEEE TKDE 31(2) (2019).

27.

Mehta ,

L.C.

Duke and

Rai , Stochastic blockmodels meet graph neural networks, in: ICML, 2019, pp. 4466–4474.

28.

Mollgaard ,

Zettler ,

Dammeyer ,

M.H.

Jensen ,

Lehmann and

Mathiesen , Measure of node similarity in multilayer networks, PLoS ONE 11(6) (2016), e0157436. doi:10.1371/journal.pone.0157436.

29.

P.J.

Mucha and

M.A.

Porter , Communities in multislice voting networks, Chaos 20 (2010), 041108. doi:10.1063/1.3518696.

30.

P.J.

Mucha ,

Richardson ,

Macon ,

M.A.

Porter and

J.-P.

Onnela , Community structure in time-dependent, multiscale, and multiplex networks, Science 328(5980) (2010), 876–878. doi:10.1126/science.1184819.

31.

Murata , Comparison of inter-layer couplings of multilayer networks, in: International Conference on Signal-Image Technology and Internet-Based Systems, 2015.

32.

Pramanik ,

Tackx ,

Navelkar ,

J.-L.

Guillaume and

Mitra , Discovering community structure in multilayer networks, in: International Conference on Data Science and Advanced Analytics, 2017.

33.

Salehi ,

Sharma ,

Marzolla ,

Magnani ,

Siyari and

Montesi , Spreading processes in multilayer networks, IEEE TNSE 2(2) (2015).

34.

Su ,

Xue ,

Liu ,

Wu ,

Yang ,

Zhou ,

Hu ,

Paris ,

Nepal ,

Jin ,

Q.Z.

Sheng and

P.S.

Yu , A Comprehensive Survey on Community Detection with Deep Learning, CoRR, 2021, arXiv:2105.12584. doi:10.1109/TNNLS.2021.3137396.

35.

Tagarelli ,

Amelio and

Gullo , Ensemble-based community detection in multilayer networks, Data Min Knowl Disc 31 (2017), 1506–1543. doi:10.1007/s10618-017-0528-8.

36.

Tang ,

Wang and

Liu , Uncovering groups via heterogeneous interaction analysis, in: IEEE International Conference on Data Mining, 2009.

37.

Tu ,

G.-P.

Jiang ,

Song and

Zhang , Novel multiplex PageRank in multilayer networks, IEEE Access Digital Object Identifier (2018). doi:10.1109/ACCESS.2018.2807778.

38.

Wang and

Zou , A new centrality measure of nodes in multilayer networks under the framework of tensor computation, Applied Mathematical Modelling (2018).

39.

Wang ,

Zhang ,

Wei ,

Pei and

Zheng , On the stability of multilayer Boolean networks under targeted immunization, in: KDD, 2009.

40.

Wang,

Robins,

Pattison and

Lazega, Exponential random graph models for multilevel networks, Social networks 35 (2013), 96–115. doi:10.1016/j.socnet.2013.01.004.

41.

A.W.

Wolfe , In the ngombe tradition: Continuity and change in the Congo, Am. Anthropol. 65 (1963), 137–138. doi:10.1525/aa.1963.65.1.02a00120.

42.

Wu ,

Pu ,

Li and

Cao , Traffic dynamics on multilayer networks, Digital Communications and Networks 6(1) (2020), 58–63, ISSN 2352–8648. doi:10.1016/j.dcan.2018.10.011.

43.

Xiao ,

Zhang ,

Qi.

Li and

Liub , MM-SIS: Model for multiple information spreading in multiplex network, Physica A: Statistical Mechanics and its Applications 513 (2019), 135–146. doi:10.1016/j.physa.2018.08.169.

44.

Zhang ,

D.T.

Nguyen ,

Zhang and

M.T.

Thai , Least cost influence maximization across multiple social networks, IEEE/ACM Transactions On Networking 24(2) (2016). doi:10.1109/TNET.2015.2404575.

45.

Zhu ,

Tang and

Tang , Pricing influential nodes in online social networks, Proc. VLDB Endow. 13(10) (2020), 1614–1627, ISSN 2150-8097. doi:10.14778/3401960.3401961.