SYSTEMS AND METHODS OF HIERARCHICAL COMMUNITY DETECTION IN GRAPHS

摘要

There is provided an apparatus for detecting communities within a graph, comprising: a processor configured to compute the following cycle: creating a directed Decoupling graph of communities of vertices from computed possible moves between communities of the graph, filtering edges of the directed Decoupling graph to obtain respective communities each including one of: incoming edges to vertices of the respective community, or outgoing edges from vertices of the respective community, and updating vertices of the marked graph with community labels from edges of the filtered directed Decoupling graph, wherein a packed graph created by merging vertices of each community of the filtered directed Decoupling graph and merging multiple edges between couples of vertices of the packed graph into a single edge denotes the computed hierarchical communities of the marked graph. The graph eventually converges to a solution when executed in a parallel and/or distributed computing system.