Journal of Advanced Statistics

Download PDF (1206.5 KB) PP. 78 - 95 Pub. Date: June 13, 2017

DOI: 10.22606/jas.2017.22002

• Tai-Chi Wang
  National Center for High-Performance Computing, National Applied Research Laboratories, Taiwan
• Frederick Kin Hing Phoa^*
  
  Institute of Statistical Science, Academia Sinica, Taiwan
• Yuan-Lung Lin^*
  
  Institute of Statistical Science, Academia Sinica, Taiwan

Network data have become very popular with the growth of technologies and social applications such as Twitter and Facebook. However, few visualization tools have been created for exploring large-scale networks. We propose a simple and quick procedure to explore a network in this study. The algorithm changes the edge representation based on the complement of a simple graph and the partition method of vertex coloring. Furthermore, the colors provide additional information on top of the partitions. Our proposed method is demonstrated in some famous networks.

Visualization, complement of graph, greedy algorithm, network partition, N-clique.

[1] P. Erdos and A. Rényi, “On random graphs,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290–297, 1959.

[2] D. J. Watts and S. H. Strogatz, “Collective dynamics of aesmall-worldaenetworks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.

[3] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” science, vol. 286, no. 5439, pp. 509–512, 1999.

[4] P. Shannon, A. Markiel, O. Ozier, N. S. Baliga, J. T. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker, “Cytoscape: a software environment for integrated models of biomolecular interaction networks,” Genome research, vol. 13, no. 11, pp. 2498–2504, 2003.

[5] M. Bastian, S. Heymann, M. Jacomy et al., “Gephi: an open source software for exploring and manipulating networks.” ICWSM, vol. 8, pp. 361–362, 2009.

[6] G. Csardi and T. Nepusz, “The igraph software package for complex network research,” InterJournal, Complex Systems, vol. 1695, no. 5, 2006.

[7] T. M. Fruchterman and E. M. Reingold, “Graph drawing by force-directed placement,” Software: Practice and experience, vol. 21, no. 11, pp. 1129–1164, 1991.

[8] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on scientific Computing, vol. 20, no. 1, pp. 359–392, 1998.

[9] S. Arora, S. Rao, and U. Vazirani, “Expander flows, geometric embeddings and graph partitioning,” Journal of the ACM (JACM), vol. 56, no. 2, p. 5, 2009.

[10] S. Wasserman and K. Faust, Social network analysis: Methods and applications. Cambridge university press, 1994, vol. 8.

[11] M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical review E, vol. 69, no. 2, p. 026113, 2004.

[12] P. J. Bickel and A. Chen, “A nonparametric view of network models and newman–girvan and other modularities,” Proceedings of the National Academy of Sciences, vol. 106, no. 50, pp. 21 068–21 073, 2009.

[13] M. S. Handcock, A. E. Raftery, and J. M. Tantrum, “Model-based clustering for social networks,” Journal of the Royal Statistical Society: Series A (Statistics in Society), vol. 170, no. 2, pp. 301–354, 2007.

[14] N. A. Heard, D. J. Weston, K. Platanioti, and D. J. Hand, “Bayesian anomaly detection methods for social networks,” The Annals of Applied Statistics, vol. 4, no. 2, pp. 645–662, 2010.

[15] L. Tang and H. Liu, “Community detection and mining in social media,” Synthesis Lectures on Data Mining and Knowledge Discovery, vol. 2, no. 1, pp. 1–137, 2010.

[16] D.-Z. Du and P. M. Pardalos, Handbook of combinatorial optimization: supplement. Springer Science & Business Media, 1999, vol. 1.

[17] F. T. Leighton, “A graph coloring algorithm for large scheduling problems,” Journal of research of the national bureau of standards, vol. 84, no. 6, pp. 489–506, 1979.

[18] P. Hell and J. Ne?etril, “On the complexity of< i> h-coloring,” Journal of Combinatorial Theory, Series B, vol. 48, no. 1, pp. 92–110, 1990.

[19] P. Briggs, K. D. Cooper, and L. Torczon, “Improvements to graph coloring register allocation,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 16, no. 3, pp. 428–455, 1994.

[20] M. Thorup, “All structured programs have small tree width and good register allocation,” Information and Computation, vol. 142, no. 2, pp. 159–181, 1998.

[21] A. Kosowski and K. Manuszewski, “Classical coloring of graphs,” Contemporary Mathematics, vol. 352, pp. 1–20, 2004.

[22] W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of anthropological research, pp. 452–473, 1977.

[23] A. Hertz and D. de Werra, “Using tabu search techniques for graph coloring,” Computing, vol. 39, no. 4, pp. 345–351, 1987.

[24] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning,” Operations research, vol. 39, no. 3, pp. 378–406, 1991.

[25] P. Galinier and J.-K. Hao, “Hybrid evolutionary algorithms for graph coloring,” Journal of combinatorial optimization, vol. 3, no. 4, pp. 379–397, 1999.

[26] D. B. West et al., Introduction to graph theory. Prentice hall Upper Saddle River, 2001, vol. 2.

[27] R. J. Light and B. H. Margolin, “An analysis of variance for categorical data,” Journal of the American Statistical Association, vol. 66, no. 335, pp. 534–544, 1971.

[28] V. D. Blondel, J.-L. Guillaume, J. M. Hendrickx, and R. M. Jungers, “Distance distribution in random graphs and application to network exploration,” Physical Review E, vol. 76, no. 6, p. 066101, 2007.

[29] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations,” Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396–405, 2003.

[30] D. Lusseau, “The emergent properties of a dolphin social network,” Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, no. Suppl 2, pp. S186–S188, 2003.

[31] D. E. Knuth, D. E. Knuth, and D. E. Knuth, The Stanford GraphBase: a platform for combinatorial computing. Addison-Wesley Reading, 1993, vol. 37.

[32] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002.

[33] J. Leskovec and J. J. Mcauley, “Learning to discover social circles in ego networks,” in Advances in neural information processing systems, 2012, pp. 539–547.