Introduction
Related work
Our approach
-
First a breadth-first search (BFS) [18] is added to the algorithm before going thorough the initial distance calculations. It helps the program run almost ten percent faster (an algorithm for traversing or searching tree or graph data structures). It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors [18].
-
A new algorithm called “Community Ranker” is introduced. As the name suggest, CR (Community Ranker) method finds a value for each community that was found by Algorithm 1. How communities have been ranked is provided in "Algorithm" section by Algorithm 2.
Data set | Attractor | Optimized Attractor | OA and BFS |
---|---|---|---|
Karate Club | 0.012278 | 0.012091 | 0.011930 |
American Football | 0.119706 | 0.101960 | 0.101330 |
Polbooks | 0.149019 | 0.138020 | 0.137216 |
Friendship | 446.488900 | 325.466700 | 305.337700 |
Amazon | 379.636510 | 297.4342910 | 285.840700 |
Road | 327.805610 | 317.141900015 | 303.112400 |
Preliminaries
Notations
Algorithm
Analysis
Time complexity analysis
Experimental analysis
Data set
Data set | Number of nodes | Number of edges |
---|---|---|
Karate Club | 34 | 78 |
American Football | 115 | 613 |
Polbooks | 105 | 441 |
Friendship | 58,228 | 214,078 |
Amazon | 334,863 | 925,872 |
Road | 1,088,092 | 1,541,898 |
Discussion and future work
Data set | Attractor | Modularity |
---|---|---|
Karate Club | 1 | 0.916128 |
American Football | 1 | 0.952536 |
Polbooks | 1 | 0.854031 |
Data set | Num of comm | Max nodes | Min nodes | Process time |
---|---|---|---|---|
Karate Club | 3 | 17 | 1 | 0.001000 |
American Football | 12 | 14 | 5 | 0.001000 |
Polbooks | 4 | 44 | 1 | 0.001000 |
Friendship | 15,280 | 15,280 | 1 | 0.132000 |
Amazon | 33,931 | 1494 | 1 | 0.613000 |
Road | 22,978 | 876,500 | 1 | 0.992000 |
Conclusion
Notation | Definition and description |
---|---|
G | Given graph |
N, n | Set of nodes, node |
L, l
| Set of links, link |
C, c | Set of community, community |
\(\eta\)
| Number of nodes in each C |
\(R_{c}\)
| Rank of community c |
\(\gamma\)
| Number of edges between two C |
\(e_{b}\)
| Designated edges between two C |
\(n_{s}^e \;{\rm and}\; n_{t}^e\)
| Nodes on the side of an edge |
S | Similarity value |
s, e | Start and end node |
m, x | Mutual, exclusive neighbor |
\(\varUpsilon\)
| Neighboring set |