International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 11, No. 11, 8 Nov. 2019
Cover page and Table of Contents: PDF (size: 935KB)
Graph Abstraction Based on Node Betweenness Centrality
Full Text (PDF, 935KB), PP.10-17
Views: 0 Downloads: 0
Author(s)
Index Terms
Graph abstraction, Network analysis metrics, Nodes betweenness centrality, Degree, Modularity
Abstract
There are many graph abstraction methods that are existed as solutions for problems of graphs visualization. Visualization problems include edge crossings and node occlusions that hide the potential existed patterns. The aim of this research is to abstract graphs using one of network analysis metrics which is node betweenness centrality. Betweenness centrality is calculated for all graph nodes. Graph abstraction is done by removing the nodes with their attached edges such that they have betweenness centrality lower than a certain examined threshold. Experiments have been conducted and results show that the proposed abstraction method can effectively reduce the complexity of the graph visualization in term of node degree. Modularity of clusters after filtering is decreased but the final graph visualization is simpler and more informative.
Cite This Paper
Arwa M. Aldabobi, Riad S. Jabri, " Graph Abstraction Based on Node Betweenness Centrality", International Journal of Image, Graphics and Signal Processing(IJIGSP), Vol.11, No.11, pp. 10-17, 2019. DOI: 10.5815/ijigsp.2019.11.02
Reference
[1]William Kocay, Donald L Kreher, “Graphs, Networks and Algorithms”, Chapman and Hall/CRC, November 2016.
[2]Wayne W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups”, Journal of Anthropological Research, Vol. 33, No. 4, pp. 452-473, December 1977.
[3]Mark Newman, “Modularity and Community Structure in Networks”, Proceedings of the national academy of sciences, Vol. 103, No. 23, pp. 8577-8582, June 2006.
[4]Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, “Fast Unfolding of Communities in Large Networks”, Journal of statistical mechanics: theory and experiment, July 2008.
[5]Ivan Herman, Guy Melancon, M. Scott Marshall, “Graph Visualization and Navigation in Information Visualization: a Survey”, IEEE Transactions on visualization and computer graphics, Vol 6, No. 1, pp. 24-43, January 2000.
[6]Liu Y., Safavi T., Dighe A. and Koutra D., “Graph Summarization Methods and Applications: A Survey”, ACM Computing Surveys (CSUR), Vol. 51, No. 3, July 2018.
[7]Hu Y. and Shi L., “Visualizing Large Graphs”, Wiley Interdisciplinary Reviews: Computational Statistics, Vol. 7, No. 2, pp. 115-136, 2015.
[8]Crnovrsanin T., Muelder C.W., Faris R., Felmlee D. and Ma K.L., “Visualization Techniques for Categorical Analysis of Social Networks with Multiple Edge Sets”, Social Networks, Vol. 37, pp. 56-64, 2014.
[9]Lin C.C., Huang W., Liu W.Y. and Wu S.F., “A Novel Centrality-Based Method for Visual Analytics of Small-World Networks”, Journal of Visualization, pp. 1-18, 2019.
[10]Zhou Z., Meng L., Tang C., Zhao Y., Guo Z., Hu M. and Chen W., “Visual Abstraction of Large Scale Geospatial Origin-Destination Movement Data”, IEEE transactions on visualization and computer graphics, Vol. 25, No. 1, pp. 43-53, 2018.
[11]Zeqian Shen, Kwan-liu Ma, Tina Eliassi-Rad, “Visual Analysis of Large Heterogeneous Social Networks by Semantic and Structural Abstraction”, IEEE transactions on visualization and computer graphics, Vol. 12, No. 6, pp. 1427-1439, September 2006.
[12]Michelle Girvan, Mark Newman, “Community Structure in Social and Biological Networks”, Proceedings of the national academy of sciences, Vol. 99, No. 12, pp. 7821-7826, June 2002.
[13]M. E. J. Newman, “Detecting Community Structure in Networks”, The European Physical Journal B-Condensed Matter and Complex Systems, Vol. 38, No. 2, pp. 321-330, June 2004.
[14]Yuntao Jia, Jared Hoberock, Michael Garland, John C. Hart, “On the Visualization of Social and Other Scale-Free Networks”, IEEE transactions on visualization and computer graphics, Vol. 14, No. 6, pp. 1285-1292, 2008.
[15]Peter Eades, “A Heuristic for Graph Drawing”, Congressus numerantium, Vol. 42, pp. 149-160, 1984.
[16]http://www-personal.umich.edu/~mejn/netdata/, accessed in January 2019.
[17]M. E. J. Newman, “Finding Community Structure in Networks using the Eigenvectors of Matrices”, Physical Review E, Vol. 74, No. 3, September 2006.
[18]Duncan J. Watts, Steven H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks”, Nature, Vol. 393, pp. 440-442, June 1998.
[19]https://github.com/gephi/gephi/wiki/Datasets, accessed in January 2019.
[20]Danai Koutra, Ankur Parikh, Aaditya Ramdas, “Algorithms for Graph Similarity and Subgraph Matching”, Proc. Ecol. Inference Conf, Vol. 17, 2011.