NGD: Filtering graphs for visual analysis

Graph visualization finds wide applications in different areas. As the popularity of social network sites is increasing, it becomes particularly useful in visual analysis of these sites. A number of algorithms for graph visualization have been developed over the past decades. The issue on how to design and develop algorithms by taking into account the characteristics of real graphs such as scale-free and hierarchical structures, however, has not been well addressed. In this paper, we extend the concept of a node degree to a node global degree for a node in a graph, and present an algorithm that computes their scores of all nodes. By taking advantage of the common structure features of real networks, two scalable extensions of this algorithm are further provided that are able to approximate computation results. Based on node global degrees, a filtering approach is presented to reduce the visual complexity of a layout. Extensive experiments have demonstrated the performance of the proposed algorithms in terms of two common evaluation metrics, as well as visualization results. In addition, we have implemented the algorithms in a prototype system, which enable users to explore a graph at continuous levels of details in real time, as evidenced by several real examples.