Email this article 
Visually Mining Relational Data
(*) Corresponding author
DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)
Abstract
Mining relational data often boils down to computing clusters, that is finding sub-communities of data elements forming cohesive sub-units, while being well separated from one another. The clusters themselves are sometimes termed “communities” and the way clusters relate to one another is often referred to as a “community structure”. Methods for identifying communities or subgroups in network data is the focus of intense research is different scientific communities and for different purposes. The present paper focuses on two novel algorithms producing multilevel community structures from raw network data. The two algorithms exploit an edge metric extending Watts's clustering coefficient to edges of a graph. The full benefit of the method comes from the multilevel nature of the community structure as it facilitates the visual interaction and navigation of the network by zooming in and out of components at any level. This multilevel navigation proves to be useful when visually exploring a network in search for structural patterns.
Copyright © 2018 Praise Worthy Prize - All rights reserved.
Keywords
References
Marcos, A. F., Muller, W., and Schumann, H., Visual knowledge discovery (special issue). Computers & Graphics, Vol. 28 n. 3 pp. 309-310, 2004.
Huband, J. M., Bezdek, J. C., and Hathaway, R. J., bigvat: Visual assessment of cluster tendency for large data sets. Pattern Recognition, Vol. 38, n. 11, pp. 1875-1886, 2005.
Aggarwal, C. C., On the use of human-computer interaction for projected nearest neighbor search. Data Mining and Knowledge Discovery, Vol. 13, n. 1, pp. 89-117, 2006.
Card, S., Mackinlay, J., and Shneiderman, B. 1999. Readings in Information Visualization. Morgan Kaufmann Publishers, San Francisco.
Herman, I., Marshall, M. S., and Melançon, G., Graph visualisation and navigation in information visualisation: A survey. IEEE Transactions on Visualization and Computer Graphics, Vol. 6, n. 1, pp. 24-43, 2000.
di Battista, G. d., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph Drawing: Algorithms for the Visualisation of Graphs. Prentice Hall.
Kaufmann, M. and Wagner, D. (Editors) 2001. Drawing Graphs, Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer.
Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proceedings of the National Academy Science USA, 99:7821-7826.
Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Physical Reviews, E 69(026113).
Alpert, C. J. and Kahng, A. B. 1995. Recent developments in netlist partitioning: A survey. Integration: the VLSI Journal, 19(1-2):1-81.
Michaud, P. 1997. Clustering techniques. Future Generation Computer System, 13:135-147.
FjÄallstrom, P. 1998. Algorithms for graph partitioning: A survey. Linkoping Electronic Articles in Computer and Information Science, 3(10). www.ep.liu.se/ea/cis/1998/010/.
Jain, A. K., Murty, M. N., and Flynn, P. J. 1999. Data clustering: a review. ACM Computing Surveys, 31(3):264-323.
Berkhin, P. 2002. Survey of clustering data mining techniques. Technical report, Accrue Software.
dos Santos, S. and Brodlie, K. 2004. Gaining understanding of multivariate and multidimensional data through visualization. Computers & Graphics, 28(3):311-325.
Herman, I., Marshall, M. S., Melançon, G., Duke, D. J., Delest, M., and Domenger, J.-P. 1999. Skeletal images as visual cues in graph visualization. In: Gröller, E., Löffelmann, H., and Ribarsky, W. (Editors), Data Visualization '99, Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization, Wien. Springer-Verlag, pages 13-22.
Herman, I., Melançon, G., and Delest, M. 1998. Tree visualisation and navigation clues for information visualisation. Computer Graphics Forum, 17(2):153-165.
Auber, D., Chiricota, Y., Jourdan, F., and Melançon, G. 2003. Multiscale navigation of small world networks. In: IEEE Symposium on Information Visualisation, Seattle, GA, USA. IEEE Computer Science Press, pages 75-81.
Auber, D., Delest, M., and Chiricota, Y. 2004. Strahler based graph clustering using convolution. In: Eighth International Conference on Information Visualisation (IV'04). IEEE Computer Society, pages 44-51.
Huang, X., Eades, P., and Lai, W. 2005. A framework of filtering, clustering and dynamic layout graphs for visualization. In: Estivill-Castro, V. (Editor), 28th Australasian Computer Science Conference. Australian Computer Society, 38.
Botafogo, R. A., Rivlin, E., and Schneiderman, B. 1992. Structural analysis of hypertexts: Identifying hierarchies and useful metrics. ACM Transactions on Information Systems, 10(2):142-180.
Henry, T. R. 1992. Interactive Graph Layout: The Exploration of Large Graphs. Phd, University of Arizona.
Newman, M. E. J. 2001. Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality. Physical Review E, 64(016132).
Chiricota, Y., Jourdan, F., and Melançon, G. 2003. Software components capture using graph clustering. In: 11th IEEE International Workshop on Program Comprehension, Portland, Oregon. IEEE / ACM, pages 217-226.
Chi, E. H. 2000. A taxonomy of visualization techniques using the data state reference model. In: IEEE Symposium on Information Vizualization. IEEE Computer Society, page 69.
Wijk, J. v. 2005. The value of visualization. In: Silva, C., Groeller, E., and Rushmeier, H. (Editors), IEEE Visualization. IEEE Computer Society, pages 79-86.
Mancoridis, S., Mitchell, B. S., Rorres, C., Chen, Y., and Gansner, E. 1998. Using automatic clustering to produce high-level system organizations of source code. In: IEEE International Workshop on Program Understanding (IWPC'98), Ischia, Italy.
Watts, D. and Strogatz, S. H. 1998. Collective dynamics of "small-world" networks. Nature, 393:440-442.
Erdös, P. and Rényi, A. 1959. On random graphs. Publ. Math. Debrecen, 6:290-297.
Erdös, P. and Rényi, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17-61.
Bollobás, B. 1985. Random Graphs. Academic Press, London.
Bornholdt, S. and Schuster, G. (Editors) 2003. Handbook of Graphs and Networks: From the Genome to the Internet. Wiley-VCH.
Dorogovtsev, S. N. and Mendes, J. F. F. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press.
Chakrabarti, D. and Faloutsos, C. 2006. Graph mining: Laws, generators, and algorithms. ACM Computing Surveys, 38(1):2.
Jaccard, P. 1912. New Phytol., 11:37-50.
Tanimoto, T. 1958. An elementary mathematical theory of classification and prediction. Technical report, IBM Report.
Willett, P., Barnard, J., and Downs, G. 1998. Chemical similarity searching. Journal of Chemical Information and Computer Sciences, 38:983-996.
Freeman, L. C. 1977. A set of measures of centrality based upon betweeness. Sociometry, 40:35-41.
Scott, J. P. 2000. Social Network Analysis: A Handbook. SAGE Publications, 2nd edition.
Goldberg, D. S. and Roth, F. P. 2003. Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Sciences of the United States of America, 100(8):4372-4376.
Zachary, W. 1977. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452-473.
Dion, D., Auber, D., Leblanc, B., and Melançon, G. 2003. Graphe d'associations verbales : élaboration et visualisation. In: Cognitique : vers une informatique plus cognitive et sociale, pages 223-232. Cépaduès-Editions.
Dion, D. 2005. Graphes d'associations verbales et réseaux petit monde (Word association network and small world networks). Master thesis, cognitive science institute, Université Victor Segalen, Bordeaux, France.
Guha, S., Rastogi, R., and Shim, K. 1999. Rock: a robust clustering algorithm for categorical attriutes. In: Proceedings of the 15th ICDE, Sydney, Australia. pages 512-521.
van Wijk, J. and van Ham, F. 2004. Interactive visualization of small world graphs. In: Munzner, T. and Ward, M. (Editors), IEEE Symposium on Information Visualisation, Austin, TX, USA. IEEE Computer Science press.
Herman, I., Marshall, M. S., and Melançon, G. 2000a. Density functions for visual attributes and effective partitioning in graph visualization. In: Roth, S. F. and Keim, D. A. (Editors), IEEE Symposium on Information Visualization (InfoVis'2000), Salt Lake City, Utah, U.S. IEEE Computer Society, pages 49-56.
Amiel, M., Melançon, G., and Rozenblat, C. 2005. Réseaux multi-niveaux : l'exemple des échanges aériens mondiaux. Mappemonde, 78.
Guimera, R., Mossa, S., Turtschi, A., and Amaral, L. A. N. 2005. The worldwide air transportation network: anomalous centrality, community structure, and cities global roles. Proceedings of the National Academy of Sciences of the United States of America, 102(22):7794-7799.
Delest, M., Fédou, J.-M., and Melançon, G. 2006. A quality measure for multi-level community structure. In: SYNASC 2006 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania.
Mitchell, B. S., Mancoridis, S., Chen, Y.-F., and Gansner, E. 1999. Bunch: A clustering tool for the recovery and maintenance of software system structures. In: ICSM. pages 50.
Auber, D. 2003. Tulip - a huge graph visualization framework. In: Mutzel, P. and Jünger, M. (Editors), Graph Drawing Software, Mathematics and Visualization Series. Springer Verlag.
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. 2004. Defining and identifying communities in networks. Proceedings of the National Acadademy of Science USA, 101:2658-2663.
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
