Permanence based Hidden Community and Graph Recovery in Social Networks ^††thanks: ^∗ Corresponding author. School of Computing, Gachon University, Republic of Korea. (email: [email protected])

We consider an undirected connected graph $G=(V,E)$, where $V$ is a set of nodes and $E$ is the set of edges of the form $(i,j)$ for $i,j\in V$. After applying a CD algorithm on $G,$ we assume that there are $k\geq 1$ detected communities and we denote a set of detected communities by $CS=\{C_{1},...,C_{k}\}.$ We also assume that there are no overlapping communities, i.e., $C_{i}\cap C_{j}=\emptyset$ for any $i\neq j.$ For each $C_{i}$, if an edge $(u,v)$ is in $C_{i},$ it is denoted by intracommunity edge whereas for an edge $(u,v)$, where $u\in C_{i}$ and $v\in C_{j}$ with $C_{i}\cap C_{j}=\emptyset$, we denote it as a intercommunity edge.

As a measure of community structure in the graph, we use the permanence proposed by Chakraborty et al.[7]. This is a vertex-centric score function that quantifies how well node $v$ is affiliated with community $C$. To see this, let $I(v)$ be the internal connections of a node $v$ within its own community and let $E_{max}(v)$ be the maximum connections of $v$ to its neighboring communities. Next, we let $C_{in}(v)$ be the fraction of actual and possible number of edges among the internal neighbors of $v$. Then, the permanence of $v$ in $G$ is given by:

where $deg(v)$ is the node degree of $v.$ This score function indicates that if the internal connectivity $I(v)$ of vertex $v$ is greater than the external connectivity $E_{max}(v)$, the corresponding value increases and forming a close clique and is divided by the degree of $v$ to normalize it [7]. As an extension, the permanence of the graph $G$ is defined by $Perm(G)=\sum_{v\in G}Perm(v,G)/|V|,$ where $|V|$ is the number of nodes in $G$. Then the graph permanence is an average of node permanence over the graph.

For community deception, the authors [8] proposed Network Deception Using Permanence Loss (NEURAL) algorithm in their work. The main idea of the algorithm is that some intracommunity or inter-community edges are updated (added or deleted) based on the permanence difference between before the update and after the edge update. To see this more precisely, we first define a permanence loss [8] of two graphs $G$ and $G^{\prime}$, where $G^{\prime}$ is the graph result from some edge update on $G,$ as follows:

Then, the goal of designing the NEURAL is to maximize the $\mathcal{P}_{l}$. For this, it is necessary to minimize the right term $Perm(G^{\prime})$ since the permanence of $G$, $Perm(G)$ is fixed if the graph is given. The NEURAL algorithm includes two main steps as depicted in Algorithm 1. Step 1 describes the process of finding an edge to add to another community in the target community. That is, for given original graph $G$, Target community $C$ and budget $B>0$, which will be used for the edge update, the NEURAL first select nodes pair $(u,v)$, for $u\in C$ and $v\in C^{\prime}$, where $C^{\prime}$ is the community of maximum external pull of $u.$ Then, it computes the permanence $Perm(u,G)$ for the original graph $G$ and $Perm(u,G^{\prime})$ for the updated graph $G^{\prime}$ with adding the edge $(u,v)$. Next, it computes the difference between them for all $u\in C$ and $v\in C^{\prime}$ and finds the maximum $(u^{*},v^{*})$ of the difference (lines 3-4). Then, it calculated the difference of permanences between the original graph $G$ and the updated graph $G^{\prime}$ as $\mathcal{P}_{l,ad}$. On the other hand, Step 2 includes the process of finding an edge to delete within the same community. In this process, similar to step 1, calculate the permanence of the selected edge to find the edge $(w^{*},z^{*})$ that maximizes the difference and put it in $\mathcal{P}_{l,de}$ (lines 6-8). ¹¹1The reason why it is possible to find edges greedily as in Step 1 and Step 2 is that all permanences satisfy submodularity as shown in [8]. Adding an edge in the inter-community and deleting an edge in the intra-community is an operation that increases the permanence gain as proven in [8], so only these two have been considered. Finally, the algorithm compares the values of $\mathcal{P}_{l,ad}$ and $\mathcal{P}_{l,de}$ obtained in this way and performs an edge update that satisfies a larger permanence gain, one budget is used (lines 9-13). This process is repeated until the total budget $B$ is exhausted, and the last updated graph is output as $G^{\prime}$.

As a simple approach to the recovery of hidden communities that applied the NEURAL algorithm, we propose a Reverse-NEURAL (R-NEURAL) in this paper. This includes the reverse application of the two cases below based on NEURAL. Before describing that, we let $G^{\prime}$ be the output graph after applying the NEURAL and let $G^{\prime\prime}$ be the graph after updating edge deleting, or adding on $G^{\prime}$ to recover the original graph $G$. Then, we introduce permanence gain, $\mathcal{P}_{g}$, as follows:

The above permanence gain seems quite similar to the permanence loss in (2). However, the goal of maximizing the permanence loss is to find $G^{\prime}$ that minimizes the permanence of the new graph $G^{\prime}$ whereas the goal of permanence gain $\mathcal{P}_{g}$ is to maximize the permanence of the graph $G^{\prime\prime}$ recovered from $G^{\prime}$. To do this, we reverse the following two in Algorithm 1, which is described in Algorithm 2.

• $(1)$

  In Step 1, since inter-community edges are newly connected in Step 1 of the NEURAL algorithm, we work to find and remove edges that exist between intercommunity. Due to the lack of knowledge of which edges have been added, R-NEURAL uses also a similar measure, permanence gain $\mathcal{P}_{g,de}$, to select edges to be deleted.

• $(2)$

  In Step 2, based on the method of finding the permanence loss while removing the intracommunity edge in NEURAL, we consider the addition of an intracommunity edge to $G^{\prime}$ and raise the permanence of $G^{\prime\prime}$ to $\mathcal{P}_{g,ad}$.

Finally, we compare $\mathcal{P}_{g,de}$ and $\mathcal{P}_{g,ad}$ and proceed with the operation for the larger one and consume one budget. We examine how well the community structure hidden by NEURAL can be recovered through this simple opposite approach.