# Local Community Detection Based on Small Cliques
## 3 Local Community Detection Algorithms Based on Small Cliques
### Triangle Based Community Expansion  
Our Triangle Based Community Expansion (TCE) algorithm maintains the shell of the community in a priority queue. The priority queue is sorted by a node score that determines how well a node is connected to the community, taking the neighborhood of the node and its neighbors into account. Our algorithm works iteratively by extracting a node from the queue and, if it improves the quality of the community, adding it to the community. If it is not added, we proceed with the node that has the next highest score and continue until no node from the current shell meets the condition. Our node score uses an edge score based on triangles. We chose triangles as they were shown to be a good indicator of community structure and are successfully used for community detection [PERSON] et al. (2014); [PERSON] et al. (2014); [PERSON] et al. (2014). Specifically, we found the edge score described by [PERSON] et al. [PERSON] et al. (2014) to perform quite well for unweighted graphs. The score is given by the following equation:  
\[\frac{|N(u)\cap N(v)|+1}{\min(\text{deg}(u)-1,\text{deg}(v)-1)} \tag{2}\]  
We adapt this score to weighted graphs by replacing the \(+1\)-term by the weight of the edge and the size of the intersection by the minimum weight of the two involved edges. Further, we removed the \(-1\) in the denominator as it is otherwise not clear what the score should be when one of the nodes has only one neighbor. Therefore, our edge score is given by the following equation:  
\[\omega(u,v)=\frac{w(u,v)+\sum_{x\in N(u)\cap N(v)}\min(w(u,x),w(v,x))}{\min( \text{deg}_{w}(u),\text{deg}_{w}(v))}. \tag{3}\]  
It can be understood as the ratio between the number/weight of actual triangles and the maximum possible number/weight of triangles. Note that for strictly positive edge weights, this edge score is also always strictly positive and at most 1. The node score is computed for a node \(u\) as:  
\[\texttt{SCORE}(u)=\frac{1}{\text{deg}(u)}\sum_{v\in N(u)\cap C}\omega(u,v), \tag{4}\]  
which is the sum of all edge scores from edges connecting the node \(u\) to the community \(C\), divided by its unweighted degree. We normalize the score by the node's unweighted degree, so that nodes with high degree do not have high scores, simply by virtue of having many edges connecting it with the community, regardless of edges, that connect it to other parts of the graph. Due to this normalization, node scores are also at most 1. By always removing the node with the maximum score from the shell, we consider adding every node in the shell to \(C\) at some time. However, using the node scores we prioritize some nodes over others, which leads to community growth in the directions of nodes with higher node scores. We add a node to the community, when adding it to the community improves the conductance of the community. We choose conductance as it intuitively captures the definition of a community and was shown to perform better than other scores in comparative study [30]. To use the original conductance score as shown in Equation (1), we need to know \(\operatorname{vol}(V\setminus C)\) in order to properly compute the conductance of a community \(C\), which requires knowledge of the entire graph's volume. As we do not want to assume this, we always use \(\operatorname{vol}(C)\) in the denominator of conductance in Equation (1). This approach mostly yields the same values as the original equation, since the community is usually small in relation to the whole graph. We show the pseudo-code of our algorithm TCE in Algorithm 1. It takes a graph \(G\) with edge weights \(w\) and a seed node \(s\). For simplicity we assume access to the whole graph here, however the algorithm does not actually access the whole graph but only a local neighborhood of the nodes added to the community. It begins by initializing the community \(C\) with \(s\) and the shell \(S\) as \(N(s)\), the neighbors of \(s\) (lines 1,2).