# Local Community Detection Based on Small Cliques
## 2 Density-Based Local Community Detection Algorithms
### Gce M/l  
One of the simplest schemes of local community detection is expanding a community by adding in each step the node of the shell that leads to the highest quality improvement of the community. In each step, the next node is selected by iterating over all nodes in the shell of the community. We examine the two quality measures proposed for this algorithm by [4]: The M measure [29] and the L measure [17]. The M measure is defined as the number of internal edges of the community divided by the cut of the community. This can be trivially generalized to weighted graphs by taking the sum of the edge weights instead of the number of edges:  
\[M(C):=\frac{\text{vol}_{w}(C)-\text{cut}_{w}(C)}{2\cdot\text{cut}_{w}(C)}\]  
Large values of the M measure indicate internally dense and well-separated communities. It was shown [4], that maximizing the M measure is actually equivalent to minimizing the conductance of the community as long as the volume of the community is smaller than the volume of its complement. The _conductance_ of a community \(C\) is defined as:  
\[\text{conductance}(C)=\frac{\text{cut}_{w}(C)}{\min(\text{vol}_{w}(C),\text{ vol}_{w}(V\setminus C))}. \tag{1}\]  
The L measure is defined using two terms, an internal and an external part. The internal part \(L_{in}\) is defined as the internal edge weights divided by the size of the community:  
\[L_{in}:=\frac{\text{vol}_{w}(C)-\text{cut}_{w}(C)}{|C|}\]  
The external part \(L_{ex}\) is defined as the cut of the community divided by the size of the boundary:  
\[L_{ex}:=\frac{\text{cut}_{w}(C)}{|B(C)|}\]  
The L measure is then the internal divided by the external L measure, i.e., \(L:=L_{in}/L_{ex}\). Note that if a community has no internal nodes, i.e., all nodes are adjacent to at least a node outside the community, this is actually equivalent to the M measure as then \(|C|=|B(C)|\). Therefore, large values of the L measure again indicate internally dense and externally well-separated communities. Implementation Details  
To expand the community, we need to determine which node of the shell will lead to the maximum improvement of the quality measure. In order to allow to compute this in constant time per node in the shell, we store for every node in the shell the sum of the edge weights towards the community and the sum of the remaining edge weights. This allows to determine the best candidate for the M measure in a single scan over the shell. Whenever we add a node to the community, we iterate over its neighbors and update their values. When a node is not yet in the shell, we also need to determine its initial external degree, which is its degree minus the weight of the edge through which we discovered the node. For unweighted graphs our graph data structure already stores the degree so this is possible in constant time, for weighted graphs we need to iterate over the neighbors to determine the weighted degree. Therefore, for unweighted graphs we get a total running time of \(\mathcal{O}(\text{vol}(C)+|C|\cdot|S|)\), where \(C\) is the final community and \(S\) is the largest shell encountered during the execution of the algorithm. For weighted graphs, we get an additional running time of \(\mathcal{O}(\text{vol}(S(C)))\) if the weighted degrees are not pre-computed. For the L measure we additionally need to be able to tell how much the boundary will change when we add a node \(u\) of the shell to the community \(C\). This depends on two factors: (a) if \(u\) has any external neighbors, the boundary size is increased by 1, (b) if \(u\) has any neighbors in \(C\) whose only external neighbor is \(u\), then these nodes will no longer be part of the boundary. The first factor can be easily determined by looking at the external degree of \(u\). For the second factor, we maintain two counters: For every node \(u\) in the boundary we store how many external neighbors \(\text{ex}(u)\) it has.