# Deep Link Entropy for Quantifying Edge Significance in Social Networks
## 2 Materials and Methods
Because we consider \(\mathcal{G}\) as an undirected graph, \(\mathbf{G}\) and therefore \(\mathbf{S}\) are symmetric, so that the problem can be reduced to finding \(X\) in the minimization  
\[\min_{\mathbf{X}\geq 0}\left\|\mathbf{G}-\mathbf{X}\mathbf{X}^{\top}\right\|_{F}^ {2} \tag{5}\]  
with \(\mathbf{X}\leftarrow\mathbf{X}\mathbf{S}^{\mathbf{1/2}}\), which can be done through the iteration [29]. \[\mathbf{X}_{ik}\leftarrow\mathbf{X}_{ik}\Bigg{(}\frac{1}{2}+\frac{(\mathbf{ G}\mathbf{X})_{ik}}{\big{(}2\mathbf{X}\mathbf{X}^{\top}\mathbf{X}\big{)}_{ik}} \Bigg{)}. \tag{6}\]  
Finally, normalizing the rows of \(\mathbf{X}\), each element \(\mathbf{X}_{ik}\) gives us the probability that \(i\)-th node is a member of \(k\)-th community. In the simulations, \(\mathbf{X}\) is initially taken as a random matrix, which potentially affects the results. However, we update the ranking of the significance of edges in each step (i.e., each removal) and this is achieved by a new random \(X\) matrix. Hence, -plausibly similar to a random walk process-, including not a single but too many initially random \(X\) matrices, on the average, the effect of the randomness is minimized. What is more, the minimization in Equation (5) through the iteration in Equation (6) is executed a thousand times. Hence, though starting with a random matrix with elements ranging from 0 to 1 each time, \(\mathbf{X}\) converges to the same result with insignificant differences in the elements. We confirmed this by repeating the simulations sufficiently many times and observing that although the results (curves of the plots) are not exactly the same in each run, the difference between the results of any two runs is practically insignificant, not affecting the overall results, i.e., the gap between DLE and LE does not shrink or expand significantly due to the randomness of \(X\) matrix. Having discovered the communities and memberships, the significance of each edge connecting the nodes \(i\) and \(j\) can be found by the Link Entropy (LE) [23] as  
\[LE_{ij}=\frac{\big{(}H(\mathbf{X_{i}})\big{)}+\big{(}H(\mathbf{X_{j}})\big{)} /2+JSD(\mathbf{X}_{i}\parallel\mathbf{X}_{j})}{2} \tag{7}\]  
through information entropy  
\[H(\mathbf{X_{i}})=-\sum\limits_{k=1}^{K}x_{ik}\log x_{ik} \tag{8}\]  
and Jensen-Shannon divergence for \(M=\frac{1}{2}(\mathbf{X}_{i}+\mathbf{X}_{j})\)  
\[JSD(\mathbf{X}_{i}\parallel\mathbf{X}_{j})=\frac{D(\mathbf{X}_{i}\parallel \mathbf{M})+D(\mathbf{X}_{j}\parallel\mathbf{M})}{2} \tag{9}\]  
with  
\[D(\mathbf{X}_{i}\parallel\mathbf{M})=\sum\limits_{k=1}^{K}x_{ik}\log\frac{x_{ ik}}{m_{k}}, \tag{10}\]  
whereas Deep Link Entropy (DLE) approach proposed in this work takes into account also the entropies \(\mathbf{X}_{i\text{,adj}}\) and \(\mathbf{X}_{j\text{,adj}}\) of the adjacent nodes of \(n_{i}\) and \(n_{j}\) of a network of \(N\) nodes, respectively, as  
\[ \begin{array}{rl}DLE_{ij}&=\frac{\big{(}H(\mathbf{X}_{i})\big{)}+\big{(}H( \mathbf{X}_{j})\big{)}/2+JSD(\mathbf{X}_{i}\parallel\mathbf{X}_{j})}{2}\\ &+\chi\Bigg{(}\sum\limits_{i\
eq j}^{N}H(\mathbf{X}_{i\text{,adj}})+\sum \limits_{j\
eq i}^{N}H(\mathbf{X}_{j\text{,adj}})\Bigg{)}\end{array} , \tag{11}\]  
where \(\chi\) is a parameter to be determined for achieving the highest performance in quantifying the significance of edges of a given network. Note that the extra terms are not added arbitrarily to achieve a better performance, but they appear as a result of our theory that the entropies of the adjacent nodes of \(n_{i}\) and \(n_{j}\) affect the significance of the \(e_{i-j}\) as well.