Abstract:
Scalability problem is a long-lasting challenge for
both information visualization and graph drawing
communities. Available graph visualization techniques
could perform well for small or medium size graphs but
they are rarely able to handle very large and complex
graphs. One of effective approach to solve this problem
is to employ graph abstraction; that is to hierarchically
partitioning the complete graph into a clustered graph. A
graph visualization technique is then applied to display
the abstract view of this clustered graph with partially
displayed detail of one or a few sub-graphs where the
user is currently focusing on. This reduces the
complexity of display and makes it easier for users to
interpret, perceive and navigate the large scale
information. In this paper, we propose a graph
clustering method which can quickly discover the
community structure embedded in large graphs and
partition the graph into densely connected sub-graphs.
The proposed algorithm can not only run fast, but also
achieve a consistent partitioning result in which a graph
is divided into a set of clusters of the similar size in terms
of their visual complexity and the number of nodes and
edges. In addition, we also provide a mechanism to
partition very dense graphs in which the number of edges
is much larger than the number of nodes.
