# Local Community Detection Based on Small Cliques
## 3 Local Community Detection Algorithms Based on Small Cliques
### Lte  
The local tightness expansion algorithm (LTE) [15] defines its similarity score \(s\) of two connected nodes \(u,v\) as follows:  
\[s(u,v):=\frac{2\cdot w(u,v)+\sum_{x\in N(u)\cap N(v)}w(u,x)\cdot w(v,x)}{\sqrt{ (1+\sum_{x\in N(u)}w^{2}(u,x))\cdot(1+\sum_{x\in N(v)}w^{2}(v,x))}}\]  
They then define the _tightness_\(T(C)\) of a community as  
\[T(C):=\frac{S_{in}^{C}}{S_{in}^{C}+S_{out}^{C}},\]  
where \(S_{in}^{C}\) is two times the sum of all internal similarities, i.e., using \(s\) as weight function, \(S_{in}^{C}=\text{vol}_{s}(C)-\text{cut}_{s}(C)\) and \(S_{out}^{C}\) is the sum of similarities between adjacent nodes inside and outside the community, i.e., \(S_{out}^{C}=\text{cut}_{s}(C)\). LTE always tries to add the node with \"the largest similarity with nodes in \(C\)\" [15]. We interpret this as the sum of the similarities of the node and all adjacent nodes in \(C\). correct This set of candidates can be efficiently maintained in a priority queue. A node is only added to the community if its tunable tightness gain is positive. This tunable tightness gain of a node \(a\) is defined as  
\[\tau_{C}^{a}(a):=\frac{S_{out}^{C}}{S_{in}^{C}}-\frac{\alpha S_{out}^{a}-S_{in }^{a}}{2S_{in}^{a}},\]  
where \(S_{in}^{a}\) is the sum of the similarities of \(a\) and all adjacent nodes in \(C\) and \(S_{out}^{a}\) is the sum of the similarities of \(a\) and all adjacent nodes outside of \(C\). When \(\tau_{C}^{a}(a)\) is not greater than \(0\), \(a\) is removed from the set of candidates. If \(a\) is added to the community, the set of candidates is updated with the neighbors of \(a\), therefore, a node may be re-added to the queue later if a neighbor of it is added to the community. Implementation Details  
The original paper [15] does not further address the calculation of the edge similarity scores but simply assumes they are available in constant time. We do not assume this but instead use an efficient triangle listing algorithm to calculate them. To allow fast triangle listing, we build and maintain a local graph data structure. For processing the whole queue, we need to know the external similarity for every node in the shell and therefore we need to be able to list all triangles a node in the shell is part of. To allow this, our local graph \(H\) is the subgraph induced by the community \(C\), its shell \(S(C)\) and the shell of the shell \(S(S(C))\). Using a hash table, we map global node ids to local, small integer node ids. Note that when a new node \(u\) is added to the community, only scores of neighbors of \(u\) are affected. Therefore, we need to either add \(u\)'s neighbors that are not in \(C\) to \(S\) or update their scores. The former means that the score of node \(v\) only consists of \(s(u,v)/\deg_{w}(v)\). The latter implies that we need an increaseKey operation with the updated score: \(\textsc{score}_{\text{new}}(v)=\textsc{score}_{\text{old}}(v)+s(u,v)/\deg_{w} (v)\). The total running time of all priority queue operations are therefore \(\mathcal{O}(\text{vol}(C)\log(n_{H}))\) where \(n_{H}\) denotes the number of nodes in \(H\). Using the \(h\)-graph data structure presented in [31], the triangle listing is possible in total time for all nodes \(\mathcal{O}(m_{H}\cdot\alpha(H))\), where \(m_{H}\) is the number of edges in \(H\) and \(\alpha(H)\) is the arboricity of \(H\). As we do not need all operations, we only maintain the list of higher-degree neighbors of every node and therefore only need a simplified version of the \(h\)-graph data structure. Note however, that, in order to add a node to \(H\), we need to check for all of its incident edges if the endpoint is in \(H\). Therefore, in our situation we get an additional expected running time of \(\mathcal{O}(\text{vol}(C\cup S(C)\cup S(S(C))))\), where vol denotes the volume in the whole graph. Whenever we add a node \(u\) to the community \(C\), we list all triangles \(u\) is part of and update the scores of its neighbors.