# Detecting the Structural Hole for Social Communities Based on Conductance-Degree
## 3 Conductance-Degree Structural Hole Detection Algorithm
### C-LPA and CD-SHA  
The original LPA has many disadvantages, such as the different sequences of vertices resulting in different results of communities. However, we solved this problem by detecting the LMCs as the original communities before we started spreading the labels from those original communities in the C-LPA.  
According to the notion of conductance, the lower the conductance, the fewer communications with others and the more information exchange within the group, and the more likely it is to be a community. The detailed process to compute the LMCs is described as Algorithm 2.  
```
0: the original Network (nodes and edges)
0:\(\phi(\mathrm{v})\) and the original Community structure
1: For each node in List do
2: Get the node's neighborhoods
3: Compute \(\phi(\mathrm{v})\)
4: End for
5: For each node \(v\) in List do
6: For each node's neighborhoods \(w\) in List do
7: if \(\phi(\mathrm{v})>\phi(\mathrm{w})\)
8: flag = false
9: continue
10: else
11: flag = true
12: End for
13: if flag = true
14: add \(v\) to result
15: flag = true
16: End For
17: Return
```  
**Algorithm 2**  
The dominant running time of the algorithm above computes the conductance of the neighbor community of each vertex \(v\in V\) and later compares it with its neighbors. We assumed that there were \(n\) vertices and each vertex had \(m\) neighbors, and it would take \(O(mn)\) time. In real social networks, according to the heavy-tailed degree distributions, most nodes have few neighbors, and least nodes have many neighbors, and it is true that \(m<<n\). We previously computed the conductance for structural holes, so there is little extra cost.  
By the end of Algorithm 2, we identified several independent LMCs. Next, we assigned each LMC a unique label and allocated a random label to the other nodes, as is illustrated in the left side of Figure 4. Next, we started the C-LPA with the LMCs. A simplified overview of the process is shown in Figure 4. The right side of the graph shows the situation after the C-LPA is executed. Different colors represent different communities.  
Figure 4: Illustration of the C-LPA. (1) Assign each LMC a unique label and allocate a random label to the other nodes; (2) Start the label propagation and detect the communities.  
For the CD-SHA, we defined the structural holes (SHs) to satisfy Equation (5) and across communities; as represents the CD-score.  
\[\forall\
u\in\text{SH},s_{\
u}>s_{neighbor} \tag{5}\]  
```
1:Network
2:Community structural and structural holes
3:Allocate unique labels to each LMC
4:Allocate random labels to the other nodes
5:Initialize the List (LMCs are in the front of the List and the other nodes are in the back)
6:While Current Labels! = Last Time Labels do
7:For each node in List do
8:Compute the Neighbor nodes' community label
9:Update the label
10:if on the edge
11:compare the CD-score
12:End for
13:End While
14:Return
```  
**Algorithm 1** CD-SHA  
While executing the C-LPA, we compared each node's CD-score with its neighbors and found those nodes that did not have a lower CD-score than their neighbors as structural hole candidates. If a candidate crossed at least two communities, we marked it as a structural hole spanner. The CD-score of the vertex told us which nodes exchanged more messages in a social network and the C-LPA informed us about the communities in the network. By the end of the CD-SHA, we identified communities with different labels and structural holes. The algorithm required a linear time similar to that of the LPA.