Computer Science – Data Structures and Algorithms
Scientific paper
2007-12-07
Phys. Rev. E 77,046112 (2008)
Computer Science
Data Structures and Algorithms
7 pages, parts of text rewritten, illustrations and pseudocode representation of algorithms added
Scientific paper
10.1103/PhysRevE.77.046112
Identifying strongly connected substructures in large networks provides insight into their coarse-grained organization. Several approaches based on the optimization of a quality function, e.g., the modularity, have been proposed. We present here a multistep extension of the greedy algorithm (MSG) that allows the merging of more than one pair of communities at each iteration step. The essential idea is to prevent the premature condensation into few large communities. Upon convergence of the MSG a simple refinement procedure called "vertex mover" (VM) is used for reassigning vertices to neighboring communities to improve the final modularity value. With an appropriate choice of the step width, the combined MSG-VM algorithm is able to find solutions of higher modularity than those reported previously. The multistep extension does not alter the scaling of computational cost of the greedy algorithm.
Caflisch Amedeo
Schuetz Philipp
No associations
LandOfFree
Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-120869