Figure 1
Example of a social network. (For interpretation of the references to color in this and following figure legend, the reader is referred to the web version of this article.).
Table 1
The algorithm of Triad Percolation Method (TPM).
| Algorithm 1: TPM(G, α) | |
|---|---|
| Input: G: a social network; α: belonging coefficient threshold | |
| Output: a community list comm_lst | |
| 1. | close_triad = locates all close-triads from social network G |
| 2. | open_triad = locates all open-triads from social network G |
| 3. | adj_lst = ∅: a list of adjacent triads that expand from a specific seed triad |
| 4. | comm_lst = ∅: a list of adj_lst, and eventually form a community list |
| 5. | while close_triad ≠ ∅: //start to generate initial communities by expanding seeds |
| 6. | seed_close_triad = select a close-triad with the largest sum of degree of three nodes from close_triad |
| 7. | adj_lst.append(seed_close_triad) |
| 8. | close_triad.remove(seed_close_triad) |
| 9. | for itm_clo in close_triad: |
| 10. | if itm_clo is adjacent to a triad in comm_lst: |
| 11. | adj_lst.append(itm_clo) |
| 12. | close_triad.remove(itm_clo) |
| 13. | for itm_opn in open_triad: |
| 14. | if itm_opn is adjacent to a triad in adj_lst and extDegree(itm_opn)≤2: |
| 15. | adj_lst.append(itm_opn) |
| 16. | open_triad.remove(itm_opn) |
| 17. | comm_lst.append(adj_lst) |
| 18. | adj_lst = ∅ |
| 19. | while open_triad ≠ ∅: |
| 20. | seed_open_triad = select an open-triad from open_triad |
| 21. | adj_lst.append(seed_open_triad) |
| 22. | open_triad.remove(seed_open_triad) |
| 23. | for itm_opn in open_triad: |
| 24. | if itm_opn is adjacent to a triad in adj_lst and extDegree(itm_opn)≤2: |
| 25. | adj_lst.append(itm_opn) |
| 26. | open_triad.remove(itm_opn) |
| 27. | comm_lst.append(adj_lst) |
| 28. | adj_lst = ∅ |
| 29. | while open_triad ≠ ∅: |
| 30. | seed_open_triad = select an open-triad from open_triad |
| 31. | adj_lst.append(seed_open_triad) |
| 32. | open_triad.remove(seed_open_triad) |
| 33. | for itm_opn in open_triad: |
| 34. | if itm_opn is adjacent to a triad in adj_lst and extDegree(itm_opn)≤2: |
| 35. | adj_lst.append(itm_opn) |
| 36. | open_triad.remove(itm_opn) |
| 37. | comm_lst.append(adj_lst) |
| 38. | adj_lst = ∅ |
| 39. | for itm_opn in open_triad: |
| 40. | comm_lst.append(itm_opn) |
| 41. | Convert the items in comm_lst into the corresponding node set // initial communities generation end here |
| 42. | A pair of initial communities with, and are selected from comm_lst, merged into a newer, larger community. Repeat this process until there is no any pair of communities meet the requirement of. BC (Ci, Ck) > α. |
| 43. | Output the result communities in comm_lst |
Table 2
The properties and settings of each social network.
| Network | # nodes | # edges | # comm. | α |
|---|---|---|---|---|
| Karate Club [21] | 34 | 78 | 2 | 0.35 |
| Dolphins [22] | 62 | 159 | 2 | 0.25 |
| Facebook [23] | 333 | 2519 | 8 | 0.16 |
| Cora1 | 2708 | 5249 | 293 | 0.29 |
| LFR2 | 500,000 | —3 | 500 | 0.32 |
[i] 1 Download URL: https://linqs.soe.ucsc.edu/data.
2 Download URL: http://santo.fortunato.googlepages.com/benchmark.tgz.
3 The amount of edges corresponding to different mixing parameter mu (mu ∈ [0.1,0.9]) is 15367853, 14359862, 15116857, 11368975, 12584676, 15632564, 11354862, 12758439 and 14865724, respectively. Under the premise of the same parameters settings, however, it is important to note that the number of network edges obtained by running the LFR software multiple times is significantly different.
Figure 2
The Zachary’s Karate club network and its community organization. Different community rendered in different color, the nodes and links that belong to same community rendered in same color, and the red nodes are overlaps. (a) Community structure detected by TPM. (b) The corresponding community organization discovered by CPM.
Figure 3
The bottlenose dolphins benchmark network and its community structure. Different communities rendered in different color, the nodes and links belong to same community rendered in same color. The red nodes are overlaps. (a) Community structure detected by TPM. (b) The corresponding community organization discovered by CPM.
Figure 4
The Facebook ego-network and its corresponding community structure. Different communities rendered in different color, the nodes and links belong to same community rendered in same color. Red overlapping nodes are overlaps. (a) Community structure detected by TPM. (b) The corresponding community organization discovered by CPM.
Figure 5
Comparative experiments on benchmark networks generated by LFR software.