# Deep Link Entropy for Quantifying Edge Significance in Social Networks
## 2 Materials and Methods  
In order to design a quantification strategy for the edges of a network, the first step is to discover the communities of the network, which is a crucial problem in a wide range of disciplines from sociology to biology and computer science. [PERSON] has provided a comprehensive review of the algorithms in the literature to address this problem [26]. We choose to apply one of the most successful methods, namely the non-negative matrix factorization (NMF) method [24; 27; 28] to discover the communities. Note that the main purpose of this work is to quantify the significance of edges for global connectivity and diffusion dynamics. Detecting communities and nodes' community memberships is a preliminary step of the algorithm. Next, we quantify the edges according to our DLE approach, as detailed below. To test the performance of our approach by comparing it to the original LE [23], in addition to the same community discovery algorithm, we follow exactly the same strategy to remove the most significant edge from the network and calculate \(R_{\text{GC}}\), the fraction of nodes of the largest connected group. However, removing each edge results in a new network that might possibly have a different community structure and a new ranking of edge significance. Hence, before removing the next most significant edge in each step, we first apply NMF to discover the communities again and then quantify and rank the significance of the existing edges. As illustrated in the flowchart in Figure 1, we repeat this _update the ranking and remove the currently most significant edge_ procedure until there is no edge left in the network. We consider an undirected graph \(\mathcal{G}\) consisting of \(k\) unconnected communities, each of size \(p_{1},p_{2},\ldots p_{k}\), where the weights of the edges in each community is \(s_{i}\). \(\mathbf{S}_{i}\) representing a \(p_{i}~{}\times~{}p_{i}\) matrix (with elements \(s_{i}\)), \(\mathbf{X}\) representing the cluster membership, \(\mathbf{G}\) representing the adjacency matrix of graph \(\mathcal{G}\), can be factorized as \(\mathbf{G}=\mathbf{X}\mathbf{S}\mathbf{X}^{\top}\) where  
\[\mathbf{G}= \begin{bmatrix}\mathbf{S}_{1}&0&\ldots&0\\ 0&\mathbf{S}_{2}&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&\mathbf{S}_{k}\end{bmatrix} ,\quad\mathbf{X}= \begin{bmatrix}1&0& \ldots&0\\ \vdots&0&\ldots&0\\ 1&0&\ldots&0\\ 0&1&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&1\end{bmatrix} , \tag{1}\]and  
\[\mathbf{S}= \begin{bmatrix}s_{1}&0&\ldots&0\\ 0&s_{2}&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&s_{k}\end{bmatrix} . \tag{2}\]  
Here, diagonality of \(\mathbf{G}\) and orthogonality of the columns of \(X\) is due to unconnect-edness of the communities. However in real applications, especially in social networks, communities are connected through some individuals, who are connected also to the individuals of some other networks. Hence, rather than the simple factorization, NMF can be used for discovering the communities by minimizing the loss  
\[\min_{\mathbf{X}\geq 0,\ \mathbf{S}\geq 0}L(\mathbf{G},\mathbf{X}\mathbf{S} \mathbf{X}^{\top}) \tag{3}\]  
where the loss function can be defined as  
\[L(A,B)=\left\|A-B\right\|_{F}^{2}=\sum_{ij}(A_{ij}-B_{ij})^{2}. \tag{4}\]  
Figure 1: Flowchart of the present strategy, where the communities are discovered and the significance of edges are ranked in every step for removing the _currently_ most significant edge each time, until all the edges are removed. In each step, \(R_{GC}\), the fraction of nodes of the largest component is calculated for analyzing the performance of the approaches for quantifying the edge significance.