Motif adjacency matrix and spectral clustering of directed weighted networks

1.   Introduction

Network science can help us to understand complex systems, and a common task of the analysis of networks is clustering ^[1]. The process of dividing a set into groups of similar elements is called clustering. Spectral clustering ^[2] is based on the spectral graph theory. By selecting some partition criterion ^[3,4], the objective function can be generated. The minimization of the objective function is closely related to the eigenvalues and eigenvectors of the Laplacian matrix ^[5]. Eventually, the problem becomes using the eigenvectors of the Laplacian matrix to divide the network. Spectral clustering has become a very popular clustering algorithm ^[6,7]. Unfortunately, most spectral clustering algorithms only operate on undirected networks because the adjacency matrix of a directed network is asymmetric. A common approach to clustering in directed networks is to build a symmetric adjacency matrix from the original asymmetric matrix ^[8].

The network motif ^[9] is a pattern of some kind of interconnection found in a complex network that is significantly higher than the number of interconnections in a random network. For the 13 three-node motifs of directed networks, according to the types of motifs, they can be divided into triangular motifs (closed subgraphs) and two-hop-path motifs (open subgraphs). In recent years, the traditional clustering method has begun to consider the motif of networks ^[10]. On the basis of ensuring the internal similarity of the subgraph ^[11], the traditional graph division should make sure the number of edges to be cut is as small as possible. While motif-based clustering takes into account the higher-order structure of the networks. The motif-based graph division should ensure that the nodes in the cluster should be involved in more instances of the motif and avoid cutting the instances of the motif as much as possible. Thus, the objective function of the cluster has also changed. Benson et al. ^[12] converted conductance to motif-based conductance in the partition of directed unweighted networks and generalized the motif-based spectral clustering to the directed networks by the motif adjacency matrix.

The motif adjacency matrix, which is a symmetric matrix, contains the information of a certain higher-order link pattern in the networks. For the three-node motif, Benson et al. ^[12] obtained the matrix expressions of motif adjacency matrices of triangular motifs (closed subgraphs) based on matrix operations. On this basis, the matrix operational method to obtain the matrix expressions of motif adjacency matrices for the remaining two-hop-path motifs (open subgraphs) is supplemented in this paper, and we use the lower triangular matrix to simplify the calculation difficulty. Therefore, the motif adjacency matrix expressions of all motifs in the directed network can be obtained by matrix operations.

Spectral clustering methods based on motifs are becoming increasingly important ^[13,14,15]. It is natural to search for motif-based applications for the weighted cases since weights are one of the important factors to describe the association between nodes and have a significant impact on the clustering effect of networks. For the directed weighted networks, most of the methods are to weight the motif ^[16,17,18]. In addition, a directed weighted network can be mapped to a directed unweighted network with multi-links which has the same adjacency matrix with it for analysis ^[19]. In this paper, a weighted network is considered as an unweighted network with multi-links, and by using the adjacency matrix as a bridge, the network can be mapped to an unweighted multilayer network.

This paper supplements the method of constructing matrix expressions of the motif adjacency matrix as we use the lower triangular matrix to simplify the expressions of motif adjacency matrices. And, this paper proposes a motif-based clustering algorithm for directed weighted networks (WMCA). The WMCA is tested on a benchmark network. Selecting two cluster evaluation indexes, the clustering effect of the WMCA method is compared with that of the method in ^[12] without considering the network weight on three real networks.

2.   Introduction to motif and motif-based clustering

2.1.   The three-node motif of directed networks

The motif used in this paper is a connected subgraph with three vertices. A certain connection relation of three nodes can be encoded by a binary coding matrix ${H}_{3\times 3}$. Without considering the position order of nodes, $H$ corresponds to a form of a connected subgraph, and the form of a connected subgraph is defined as a class of motif M. Figure 1 shows the types of three-node motifs in directed networks and their corresponding coding matrices. In the coding matrices, select the left node as node 1, the upper node as node 2 and the lower node as node 3.

The composition of the motifs is independent of the position order of the nodes, so the representation of the coding matrix is not unique. A connected subgraph with three vertices may have multiple coding matrices; the encoding matrices belonging to the same type of motif are permutation similarity. Take M7 as an example; its encoding matrix has three kinds, as shown in Figure 2(a). In the network shown in Figure 2(b), there are two motif instances of M7. At the same time, motif instances of other types in the network are shown in Figure 2(c).

2.2.   Motif-based spectral clustering of directed unweighted networks

Consider a directed unweighted network with $n$ nodes and a motif M; ${W}_{M} = {\left({w}_{ij}^{M}\right)}_{n\times n}$ is called the motif adjacency matrix ^[12], which ${w}_{\text{ij}}^{M}$ represents the number of instances of M in which $i$ and $j$ participate jointly. The adjacency matrix of the directed unweighted network is not a symmetric matrix, while the motif adjacency matrix is a symmetric matrix, and its element values reflect the similarity between node pairs.

Benson et al. ^[12] proposed a general motif-based clustering algorithm (MCA). And, they prove that, when the specific conductance is selected as the objective function, the conductance of the directed unweighted network is equal to the conductance of the undirected weighted network corresponding to the motif adjacency matrix, which is called the motif conductance. The node group that makes the motif conductance minimum is the optimal division. Then the partition of the directed unweighted network is converted to the partition on the undirected weighted network that the motif adjacency matrix corresponds to. Thus, based on the motif adjacency matrix to form the normalized motif Laplacian matrix, classical spectral clustering method can be used. And the motif conductance is defined as:

where $cu{t}_{M}\left(G\right)S, \overline{S}$ represents the number of the motif instances with at least one endpoint in $S$ and one endpoint in $\overline{S}$, and $vo{l}_{M}\left(G\right)S$ represents the number of instances of M formed by nodes in $S$. The lower the conductance, the better the clustering.

3.   Motif-based spectral clustering in directed weighted networks

This section introduces the motif-based spectral clustering method in directed weighted networks. The main process is shown in the Figure 3. In this section, the method of forming the expression motif adjacency matrix in directed unweighted networks is firstly introduced. Then, the method to deal with the weight of the network is introduced in order to form the motif adjacency matrix of the directed weighted network. Finally, based on the motif adjacency matrix, the directed weighted network can be clustered.

3.1.   The expression of motif adjacency matrix in directed unweighted network

When the spectral clustering method is extended to the directed network, a symmetric matrix containing node similarity information is needed to form the Laplacian matrix. The adjacency matrix of directed network is asymmetric, while the motif adjacency matrix of the network is symmetric, and contains the information of higher-order connectivity between nodes. Therefore, spectral clustering can be realized on the directed weighted network through the motif adjacency matrix. So, forming motif adjacency matrix of the directed network becomes an important tool to the motif-based clustering. Benson et al. ^[12] give a method of obtaining the expressions of the motif adjacency matrix for triangular motifs (7 types) through matrix operation, and use the k-clique enumeration algorithm to obtain the motif adjacency matrix of two-hop paths motifs (6 types). This paper supplements the method of obtaining the motif adjacency matrix by matrix operation for the two-hop paths motifs, so that the motif adjacency matrix of any kind of motif can be obtained by matrix operation.

For a directed unweighted network $G$ with adjacency matrix $A$, let $B$ and $U$ be the adjacency matrix of graphs formed by bidirectional edges and unidirectional edges, respectively ^[12]. Formally, $B = A\circ {A}^{T}$, $U = A-B$, where "$\circ$" means the Hadamard product of matrices. In mathematics, the Hadamard product is a special binary operation, where each element $i, j$ is the product of elements $i, j$ of the two original matrices ^[20]. That is, suppose $A = {\left({a}_{ij}\right)}_{m\times n}$ and $B = {\left({b}_{ij}\right)}_{m\times n}$, then the Hadamard product of them is $C = A\circ B = {\left({a}_{ij}*{b}_{ij}\right)}_{m\times n}$. When $G$ is regarded as an undirected graph $\overline{G}$, let $\overline{F}$ be the adjacency matrix corresponding to the complement graph of $\overline{G}$. An element value of 1 in $\overline{F}$ indicates that there is no edge connected between the corresponding node pair in the graph $G$, so $\overline{F}$ can be called edge-missing matrix. In terms of the matrices $U$, $B$, and $\overline{F}$, matrix expressions of 13 motif adjacency matrices can be established. Let $X, Y, Z$ represent one of $U, B$ and $\overline{F}$. The central computational kernel in these computations is $XY\circ Z$, which means these operations are similar in form, that is, multiply two matrices and then take the Hadamard product with a third matrix. Furthermore, let ${B}_{L}$ and ${\overline{F}}_{L}$ denote the lower triangular matrices of $B$ and $\overline{F}$, respectively, the matrix in some terms of the expression can be replaced by ${B}_{L}$ and ${\overline{F}}_{L}$ to simplify the calculation. For all three-node motifs, the simplified formulations that form the motif adjacency matrix ${W}_{M}$ based on matrix operations in directed unweighted networks are shown in Table 1.

In the first part of the Supplementary, the Matlab algorithm for obtaining the expression of the motif adjacency matrix for M8-M13 is given.

3.2.   The conversion of directed weighted networks

Consider a directed weighted network, the data of all nodes in the network can be represented by its adjacency matrix $A = {\left({a}_{ij}\right)}_{n\times n}$, where $n$ represents the number of nodes, ${a}_{ij}$ represents the edge weight of node $i$ to $j$. When the value of ${a}_{ij}$ is a nonnegative integer, the directed weighted network can be converted to a directed unweighted multilayer network.

Definition 1: let $A$ be a nonnegative matrix, define a mapping $\phi \left(\cdot \right)$ as follows:

where $\psi \left(\cdot \right)$ means mapping non-zero elements in a matrix to 1, and $max\left(\cdot \right)$ means taking the maximum value of the elements of a matrix.

The Mapping $\phi \left(\cdot \right)$ maps matrix $A$ to a Boolean matrix sequence ${A}_{l}, l = \mathrm{1, 2}, ..., max\left(A\right)$. If the element values in $A$ are all nonnegative integers, then has $A = {\sum }_{l = 1}^{max\left(A\right){A}_{l}}$. If such matrix $A$ is the adjacency matrix of the directed weighted network $G$, then each matrix ${A}_{l}$ can correspond to a directed unweighted network ${G}_{l}$, and ${A}_{l}$ is the adjacency matrix of the ${G}_{l}$. So, take the adjacency matrix as bridge, the mapping $\phi \left(\cdot \right)$ can map the network $G$ to a multilayer network, $G = \underset{l}{\cup }{G}_{l}$. Thus, the motif adjacency matrix in each layer of the multilayer network can be obtained by the method given in Table 1. Naturally, the motif adjacency matrix of the directed weighted network is the sum of the motif adjacency matrix of each layer.

The directed weighted network is mapped as a directed unweighted multilayer network as shown in Figure 4. Figure 4 shows a directed weighted network $G$ and its adjacency matrix $A$. Select M9 as the interested motif, and show each layer network of the multilayer network and its corresponding motif adjacency matrix corresponding to M9 in Figure 4. First-layer network is represented by ${G}_{1}$ and its adjacency matrix is ${A}_{1}$, second-layer network is represented by ${G}_{2}$ and its adjacency matrix is ${A}_{2}$, and their motif adjacency matrices corresponding to M9 are denoted by ${W}_{M}^{1}$ and ${W}_{M}^{2}$ respectively. In the first layer network, nodes $\left\{1,3,5\right\},\left\{2,3,4\right\}$ form an instance of M9 respectively; in the second layer network, nodes $\left\{1,3,5\right\},\left\{3,4,5\right\}$ form an instance of M9 respectively. According to the definition of the motif adjacency matrix, the motif adjacency matrix of each layer network is ${W}_{M}^{1}$ and ${W}_{M}^{2}$ respectively. Then the motif adjacency matrix corresponding to M9 of $G$ is ${W}_{M} = {W}_{M}^{1}+{W}_{M}^{2}$.

In the first part of the Supplementary, a program is given to obtain the expression of motif adjacency matrix for weighted networks using Matlab algorithm.

3.3.   Motif-based clustering algorithm in directed weighted networks

For directed weighted networks, computing the conductance of motif-based conductance can be translated into computing the conductance on the graph corresponding to the motif adjacency matrix. See second part of the Supplementary for proof. In this paper, choose the motifs which have more instances in the network as the motifs of interest. In the network, the motifs with more instances are considered as important motifs, which can represent the basic unit of the network structure and have a certain influence on the structure of the network, while the motifs with fewer instances in the network have a limited influence on the network structure.

Consider the clustering based on the set of motifs $\left\{\text{M1, M2, ..., Mq}\right\}$ for $q$ different motifs. Let ${W}_{{M}_{j}}, j = \mathrm{1, 2}, ..., q$ be the motif adjacency matrix of $\text{Mj}$. And let ${\alpha }_{j}$ be the weight of motif $\text{Mj}$. The value of ${\alpha }_{j}$ is the ratio of the number of $\text{Mj}$ to the total number of $q$ interested motifs. Obviously, ${\sum }_{j = 1}^{q}{\alpha }_{j} = 1$ and ${\alpha }_{j} > 0$. Then the motif adjacency matrix of the network is ${W}_{M} = {\sum }_{j = 1}^{q}{\alpha }_{j}{W}_{{M}_{j}}$. And the measures of cut and volume are simply linearly weighted sums. After forming the adjacency matrix, spectral clustering can be carried out according to the algorithm proposed by Benson et al. ^[12].

The steps of the motif-based clustering algorithms in directed weighted networks (WMCA) are as follows:

The algorithm divides the nodes into two clusters: $S$ and $\overline{S}$. For the motif conductance, ${\varphi }_{M}\left(G\right)S = {\varphi }_{M}\left(G\right)\overline{S}$, so any set of nodes can be interpreted as a cluster.

After obtaining the motif adjacency matrix of the directed weighted network, if multiple clustering is required, one can obtain multiple clusters by combining the method of Ng et al. ^[6]: Take eigenvectors of $k$ smallest eigenvalues ${z}_{1}, {z}_{2}, ..., {z}_{k}$ for ${L}_{M}$ in Step 2, and make ${y}_{ij} = \frac{{z}_{ij}}{\sqrt{{\sum }_{j = 1}^{k}{z}_{ij}^{2}}}$ to form the matrix $Y$. Then take the $ith$ row of the matrix $Y$ to embed node $i$ into ${R}^{k}$, and on the embedded nodes k-means clustering can be run.

In Sections 3.1 and 3.2, the method to deal with the weight of directed weighted networks is proposed, and the method to obtain the motif adjacency matrix expression by matrix operation is supplemented and simplified. In Section 3.3, combine the motif adjacency matrix with the spectral clustering method to get two or more clusters in directed weighted networks. The motif adjacency matrix which contains the higher-order link information between nodes can also be used in other graph clustering of directed weighted networks.

4.   Experiments

In this part, the clustering effect of WMCA method proposed in this paper is tested on a benchmark network with known partitions. Then, on the three real networks, the WMCA method and the MCA method (without considering the weight of the networks) proposed by Benson et al. ^[12] are respectively selected to cluster the networks and obtain multiple clusters. Two clustering evaluation metrics: Silhouette Coefficient (SC) ^[21] and Davies-Bouldin index (DBI) ^[22] are selected to compare the clustering effect of the two methods.

4.1.   Experiments on a benchmark social network with two clusters

The performance of WMCA method is tested on the weighted Zachary karate club network ^[23], which is often used as a benchmark network to detect the effect of network partitioning. This network has two known divisions, and the weight of the edges represents the number of contexts in which interaction took place between the two individuals involved. When the network is used, the undirected edge is regarded as a bidirectional edge, so, there are only M13 and M4 motifs in the network, and the number of instances is 880 and 115, respectively. Table 2 presents some information on the Zachary karate club network.

In Figure 5(a) shows the network diagram of the Zachary karate club network, where the thickness of the line reflects the size of the weight. The known division of the network is shown in Figure 5(b), the color of a node indicates its category. Use the WMCA method based on M13, M4 and the combination of them respectively to cluster the network, the clustering results of weighted network is obtained. Compared with the known partition results, in the M13 based clustering, node 9 is wrongly divided, as shown in Figure 5(c), while in the M4 based clustering, node 10 is divided into another group as shown in Figure 5(d). The clustering based on the combination of motif M4 and M13 gives the correct classification as shown in Figure 5(b).

Next, a further analysis of node 9 in the M13-based cluster and node 10 in the M4-based cluster is performed. The local network composed of first-order neighbors of the node is called first-order neighborhood network, and the first-order neighborhood network of nodes 9 and 10 are shown in Figure 6 respectively. The colors of the nodes in Figure 6 are the same as those in Figure 5. The set of white nodes represents cluster $S$ and the set of blue nodes represent cluster $\overline{S}$.

In Figure 6(a), considering the combination of nodes belonging to a cluster and node 9, the instances with node 9 participating of the M13 and M4 and their number are shown in Table 3, respectively. From Table 3 can know that: the strength of this higher-order link form between nodes 9, 1 and 3 is higher than that between nodes 9, 31, 33, and 34 when considering it based on the M13. And this is the opposite when considered based on M4. In Figure 6(b), node 10 is only linked to node 3, 34, and they form an instance of motif M13, and this does not impact to M4-based clustering. When the degree of node is considered, the similarity between node 10 and nodes in cluster $\overline{S}$ is higher; while considering M4-based clustering, the similarity between node 10 and nodes in the two clusters is the same because node 10 does not form an instance of M4.

4.2.   Experiments on some real networks

Select three networks in The Koblenz network collection ^[24]. The information of networks is as follows:

(1) Seventh graders network: This directed weighted network contains ratings of closeness between students at a school in Victoria. Students were asked to nominate their favorite classmates for three different activities. In the network, node represents students; If student A chooses student B to participate in an activity, there is an edge from A to B. The weights show how often this happens.

(2) Highschool network: This directed weighted network includes friendships between boys at a small high school in Illinois. A node represents a boy, boy A chooses B as his friend, then there is an edge from A to B. The weights show how often this happens.

(3) Caenorhabditis elegans (neural) network: This is a weighted network representing the neural network of Caenorhabditis elegans. In this version, the edges of the network are bidirectional, allows no multiple edges, and the given edge weights are the sum of the original edge weights.

Calculate the number of various instances of motifs in these networks. Table 3 gives some basic information about those networks and the motifs that whose instances appear relatively more often and the number of motif instances in the network. Meanwhile, the frequencies of all motif instances in the networks are shown in Figure 7.

To test the clustering effect of WMCA, the MCA method is selected for comparison. The motifs with more instances that appear in the network are selected as the motifs of interest to cluster the network. When using the MCA method, the networks are regarded as directed unweighted networks. In the non-weighted versions of these networks, the motifs M3, M6 and M11 are selected as the motifs of interest for seventh graders network, the selections of motifs for the other networks are shown in Table 4. For the WMCA method, the selections of motifs for the networks are shown in Table 4.

WMCA and MCA method are applied to these networks respectively, and the common internal clustering evaluation indexes: Silhouette Coefficient (SC) ^[21] and Davies-Bouldin index (DBI) ^[22] are selected to evaluate the effect. SC ranges between −1 and 1, where a higher SC refers to a model with more coherent clusters. And the smaller the value of DBI, the better the clustering effect. Their formats are as follows:

where $n$ is the number of nodes, $a\left(i\right)$ is the cluster cohesion which refers to the average distance between the node $i$ and all other nodes within the same cluster, and $b\left(i\right)$ is the cluster separation which refers to the average distance between the node $i$ and all other nodes in the nearest cluster. And $K$ is the number of clusters, ${s}_{u}$ and ${s}_{v}$ respectively represent intra-cluster dispersions for cluster $u$ and $v$, the average distance between each node within the cluster and its centroid. ${d}_{uv}$ is the distance between is the distance between the centroid of cluster $u$ and $v$.

Select the number of clusters within a certain range according to the number of network nodes. Under these number of clusters, the effect of two clusters is assessed by two evaluation metrics, respectively. The number of classifications $K$ and the corresponding value of two clustering evaluation indexes are shown in Figure 8. Figure 8(a), (b), (c) correspond to the cluster evaluation values of the above three networks, respectively. On the whole, the SC value of WMCA is larger than that of MCA method, especially when the number of clusters gets bigger and bigger, and the DBI values of WMCA are generally smaller than those of the MCA method. Therefore, the clustering effect of the WMCA method is better than that of the MCA method.

5.   Conclusions

Based on matrix multiplication and Hadamard product of matrices, this paper supplements the matrix expressions of motif adjacency matrix in directed unweighted networks. The central computational kernel in these computations is $XY\circ Z$. Then, through the relationship between the corresponding adjacency matrix of the networks, the directed weighted networks can be transformed into directed unweighted multilayer networks. The transformation of weighted networks in this paper is suitable for networks with integer weights. If the weights are not integers, the weights may need to be processed. Thus, the motif adjacency matrix of the network can be obtained, and the method of spectral clustering can be applied.

The advantages of the methods proposed in this paper are as follows: firstly, it provides a convenient method to deal with the weight of the network, which will be helpful to the research of other weighted networks; secondly, the clustering method is applicable to both weighted and unweighted networks, and one can select one or more motifs of interest to divide the network; finally, it is very convenient to implement the method of obtaining the expression of motif adjacency matrix and other algorithms based on motif adjacency matrix for medium scale networks. When the networks are large and sparse, these computations become slower than standard fast triangle enumeration algorithms, the parallel algorithm of sparse matrix product can improve the efficiency of calculation ^[25]. According to the structure of the motifs, the expression of the motif adjacency matrix based on matrix representation can also be extended to the cases of four-node motifs and higher order.

Overall, the complexity of the WMCA algorithm is governed by the mapping of weighted networks, the computations of the motif adjacency matrix ${W}_{M}$, an eigenvector, and the sweep cut procedure. When mapping a weighted network, it is necessary to traverse $n\times n$ elements of the adjacency matrix, whose time complexity is $O\left({n}^{2}\right)$ in theory. For forming a motif adjacency matrix, suppose ${X}_{n\times n}, {Y}_{n\times n}, {Z}_{n\times n}$, the time complexity of matrix multiplication is $O\left({n}^{3}\right)$. In theory, the time complexity of the method shown in Table 1 is $O\left({n}^{3}\right)$. And the time complexity can be optimized to $O\left({n}^{\text{2.376}}\right)$ ^[26] through the optimization of matrix operations. The complexity of the remaining steps is consistent with the method proposed by Benson et al, which is $O\left({n}^{\frac{3}{2}}\right)$.

The method (WMCA) in this paper is to cluster nodes based on the participation of nodes in forming the motif, rather than the direct links between nodes. In this paper, the directed weighted network is decomposed into a multilayer network composed of directed unweighted networks. And it has been proved in the supporting materials of Benson et al. ^[12] that the motif-based spectral clustering of directed unweighted networks can be converted into the spectral clustering problem of undirected weighted networks corresponding to the motif-based adjacency matrix, and the motif adjacency matrix of multilayer networks is the sum of the motif adjacency matrix of each layer network. Therefore, the motif-based clustering of directed weighted network can also be solved by the spectral clustering method of undirected weighted network corresponding to the motif-based adjacency matrix. In essence, the methods that take the conductivity of the matrix (graph) as the optimization objective can adopt the hierarchical processing method proposed in this paper for the directed weighted network to carry out motif-based clustering. Sieranoja et al. ^[27] introduce two new algorithms K-algorithm and M-algorithm, they are adaptations of the k-means algorithm for graph clustering. The method is applicable to undirected networks. When the direction of the network needs to be considered, the undirected weighted network based on the motif adjacency matrix of network motifs may be helpful. While a certain kind of higher-order structure is being considered in networks, some lower-order links are being ignored. In the future research, the two may be combined to consider. And when there is more than one important motif of the network, it may be worth studying which one or several motifs have the best clustering effect.

Acknowledgments

This work was supported by National Natural Science Foundation of China (grant numbers 11601267).

Conflict of interest

All authors declare no conflicts of interest in this paper.

Supplementary

(1) The Matlab algorithm "W = UWMA (A, motif)" to form the expression of the motif adjacency matrix corresponding to the motif M8-M13 is shown in Figure 1. Referring to the method "W = MotifAdjacency (A, motif)" of Benson et al. ^[12] (http://snap.stanford.edu/higher-order/), Matlab algorithm, "W = UWMA (A, motif)", that can form the expressions of motif adjacency matrix for all motifs can be given. Figure 1 also shows the algorithm "W = WMA (A, motif)" that forming the motif adjacency matrix for the directed weighted network.

(2) In a directed weighted network, mapping $\phi \left(\cdot \right)$ maps the network to a multilayer network. Let ${G}_{M}$ be the graph corresponding to the motif adjacency matrix, and ${G}^{l}$, ${W}_{M}^{l} = {\left({w}_{ij}^{l}\right)}_{n\times n}$, ${D}^{l} = {\left({d}_{ii}^{l}\right)}_{n\times n}$ and ${G}_{M}^{l}$ respectively represent the network graph, the motif adjacency matrix, the degree matrix of the motif adjacency matrix and the graph corresponding to the motif adjacency matrix of the l-layer network. Let $\left|\beta \right|$ be the number nodes that make up the motif, and when the number of nodes that make up the motif is 3, $\left|\beta \right|\text{ = 3}$.

Proposition 1: Consider the motif M, after the weighted network is mapped to the multi-layer network, the motif-based cuts and volumes of the multi-layer network are respectively equal to the sum of the motif-based cuts and volumes of each layer network, i.e (1) $cut\left({G}_{M}\right)S, \overline{S} = {\sum }_{l}cut\left({G}_{M}^{l}\right)S, \overline{S}$, (2) $vol\left({G}_{M}\right)S = {\sum }_{l}vol\left({G}_{M}^{l}\right)S$.

Proof. (1) Known from the paper ^[12] that: $cu{t}_{M}\left({G}_{M}^{l}\right)S, \overline{S} = {\sum }_{i\in S, j\in \overline{S}}{w}_{ij}^{l}$, and $cut\left({G}_{M}\right)S, \overline{S} = {\sum }_{i\in S, j\in \overline{S}}{w}_{ij}^{M}$.

Then ${\sum }_{l = 1}cu{t}_{M}\left({G}_{M}^{l}\right)S, \overline{S} = {\sum }_{l = 1}{\sum }_{i\in S, j\in \overline{S}}{w}_{ij}^{l}$, and $cut\left(\sum {G}_{M}^{l}\right)S, \overline{S} = {\sum }_{i\in S, j\in \overline{S}}{w}_{ij}^{M}$.

And ${\sum }_{l}{W}_{M}^{l} = {W}_{M}$, thus $cut\left({G}_{M}\right)S, \overline{S} = {\sum }_{l}cut\left({G}_{M}^{l}\right)S, \overline{S}$.

(2) It is known that ^[12]: $vol\left({G}_{M}^{l}\right)S = {\sum }_{i\in S}{d}_{ii}^{l}$.

Then ${\sum }_{l}vo{l}_{M}\left({G}_{M}^{l}\right)S = {\sum }_{l}{\sum }_{i\in S}{d}_{ii}^{l} = {\sum }_{l}{\sum }_{i\in S}{\sum }_{j = 1}^{n}{w}_{ij}^{l}$, and $vol\left({G}_{M}\right)S = {\sum }_{i\in S}{\sum }_{j = 1}^{n}{w}_{ij}^{M}$.

And ${\sum }_{l}{W}_{M}^{l} = {W}_{M}$, thus ${\sum }_{l}vol\left({G}_{M}^{l}\right)S = vol\left({G}_{M}\right)S$.

Proposition 2: In the multi-layer network, consider the three-node motifs, and the conductance of the directed weighted network is equivalent to the motif conductance of the network corresponding to the motif adjacency matrix, i.e $\varphi \left(G\right)S = {\varphi }_{M}\left(G\right)S$.

Proof. Known from the paper ^[12] that $vo{l}_{M}\left({G}_{l}\right)S = \frac{1}{\left|\beta \right|-1}vol\left({G}_{M}^{l}\right)S$, and$cu{t}_{M}\left(G\right)S, \overline{S} = \frac{1}{2}cut\left({G}_{M}\right)S, \overline{S}$.

Then $vo{l}_{M}\left({G}^{l}\right)S = \frac{1}{\left|\beta \right|-1}vol\left({G}_{M}^{l}\right)S$, $cu{t}_{M}\left({G}^{l}\right)S, \overline{S} = \frac{1}{2}cut\left({G}_{M}^{l}\right)S, \overline{S}$.

From Proposition 1 know: $cu{t}_{M}\left(G\right)S, \overline{S} = {\sum }_{l}cu{t}_{M}\left({G}^{l}\right)S, \overline{S}$, and $vo{l}_{M}\left(G\right)S = {\sum }_{l}vo{l}_{M}\left({G}^{l}\right)S$.

Then $cu{t}_{M}\left(G\right)S, \overline{S} = {\sum }_{l}cu{t}_{M}\left({G}^{l}\right)S, \overline{S} = \frac{1}{2}{\sum }_{l}cut\left({G}_{M}^{l}\right)S, \overline{S} = \frac{1}{2}cut\left({G}_{M}\right)S, \overline{S}$,

and $vo{l}_{M}\left(G\right)S = {\sum }_{l = 1}vo{l}_{M}\left({G}^{l}\right)S = \frac{1}{\left|\beta \right|-1}{\sum }_{l = 1}vol\left({G}_{M}^{l}\right)S = \frac{1}{\left|\beta \right|-1}vol\left({G}_{M}\right)S$.

When $\left|\beta \right| = 3$,

The proof is completed.