Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Vector Quantisation and Topology Based Graph Representation Read chapter Read first chapter

2013 | OriginalPaper | Chapter

2. Graph-Based Clustering Algorithms

Authors : Ágnes Vathy-Fogarassy, János Abonyi

Published in: Graph-Based Clustering and Data Visualization Algorithms

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The way how graph-based clustering algorithms utilize graphs for partitioning data is very various. In this chapter, two approaches are presented. The first hierarchical clustering algorithm combines minimal spanning trees and Gath-Geva fuzzy clustering. The second algorithm utilizes a neighborhood-based fuzzy similarity measure to improve k-nearest neighbor graph based Jarvis-Patrick clustering.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Vector Quantisation and Topology Based Graph Representation
next chapter Graph-Based Visualisation of High Dimensional Data
Footnotes
1
The effect of parameters \(m\) and \(\varepsilon \) was not tested, because these parameters has effects only on the GG algorithm. These parameters were chosen as it suggested in [13].
 
Literature
1.
Anders, K.H.: A hierarchical graph-clustering approach to find groups of objects. In: Proceedings 5’th ICA workshop on progress in automated map generalization, IGN, pp. 28–30 (2003)
2.
Augustson, J.G., Minker, J.: An analysis of some graph theoretical clustering techniques. J. ACM 17, 571–588 (1970)MATHCrossRef
3.
Backer, F.B., Hubert, L.J.: A graph-theoretic approach to goodness-of-fit in complete-link hierarchical clustering. J. Am. Stat. Assoc. 71, 870–878 (1976)CrossRef
4.
Barrow, J.D., Bhavsar, S.P., Sonoda, D.H.: Minimal spanning trees, filaments and galaxy clustering. Mon. Not. R. Astron. Soc. 216, 17–35 (1985)
5.
Bezdek, J.C., Clarke, L.P., Silbiger, M.L., Arrington, J.A., Bensaid, A.M., Hall, L.O., Murtagh, R.F.: Validity-guided (re)clustering with applications to image segmentation. IEEE Trans. Fuzzy Syst. 4, 112–123 (1996)CrossRef
6.
Bezdek, J., Pal, N.: Some new indexes of cluster validity. IEEE Trans. Syst. Man Cybern. 28, 301–315 (1998)CrossRef
7.
Doman, T.N., Cibulskis, J.M., Cibulskis, M.J., McCray, P.D., Spangler, D.P.: Algorithm5: a technique for fuzzy similarity clustering of chemical inventories. J. Chem. Inf. Comput. Sci. 36, 1195–1204 (1996)CrossRef
8.
9.
10.
Forina, M., Oliveros, C., Concepción, M., Casolino, C., Casale, M.: Minimum spanning tree: ordering edges to identify clustering structure. Anal. Chim. Acta 515, 43–53 (2004)CrossRef
11.
Fortune, S.: Voronoi diagrams and delaunay triangulations. In: Du, D.-Z., Hwang, F.K. (eds.), Computing in Euclidean Geometry, pp. 193–223. World Scientific, Singapore (1992)
12.
Gabriel, K., Sokal, R.: A new statistical approach to geographic variation analysis. Syst. Zool. 18, 259–278 (1969)CrossRef
13.
Gath, I., Geva, A.B.: Unsupervised optimal fuzzy clustering. IEEE Trans. Pattern Anal. Mach. Intell. 11, 773–781 (1989)CrossRef
14.
Gonzáles-Barrios, J.M., Quiroz, A.J.: A clustering procedure based on the comparsion between the k nearest neighbors graph and the minimal spanning tree. Stat. Probab. Lett. 62, 23–34 (2003)
15.
Gower, J.C., Ross, G.J.S.: Minimal spanning trees and single linkage cluster analysis. Appl. Stat. 18, 54–64 (1969)MathSciNetCrossRef
16.
Guha, S., Rastogi, R., Shim, K.: ROCK: a robust clustering algorithm for categorical attributes. In: Proceedings of the 15th international conference on data engeneering, pp. 512–521 (1999)
17.
Huang, X., Lai, W.: Clustering graphs for visualization via node similarities. J. Vis. Lang. Comput. 17, 225–253 (2006)CrossRef
18.
Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80(9), 1502–1517 (1992)CrossRef
19.
Jarvis, R.A., Patrick, E.A.: Clustering using a similarity measure based on shared near neighbors. IEEE Trans. Comput. C22, 1025–1034 (1973)CrossRef
20.
Karypis, G., Han, E.-H., Kumar, V.: Chameleon: hierarchical clustering using dynamic modeling. IEEE Comput. 32(8), 68–75 (1999)CrossRef
21.
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)MathSciNetMATHCrossRef
22.
Päivinen, N.: Clustering with a minimum spanning tree of scale-free-like structure. Pattern Recog. Lett. 26, 921–930 (2005)CrossRef
23.
Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
24.
Raghavan, V.V., Yu, C.T.: A comparison of the stability characteristics of some graph theoretic clustering methods. IEEE Trans. Pattern Anal. Mach. Intell. 3, 393–402 (1980)
25.
26.
Varma, S., Simon, R.: Iterative class discovery and feature selection using Minimal Spanning Trees. BMC Bioinform. 5, 126–134 (2004)CrossRef
27.
Vathy-Fogarassy, A., Kiss, A., Abonyi, J.: Hybrid minimal spanning tree and mixture of Gaussians based clustering algorithm. In: Lecture Notes in Computer Science: Foundations of Information and Knowledge Systems vol. 3861, pp. 313–330. Springer, Heidelberg (2006)
28.
Vathy-Fogarassy, A., Kiss, A., Abonyi, J.: Improvement of Jarvis-Patrick clustering based on fuzzy similarity. In: Masulli, F., Mitra, S., Pasi, G. (eds.) Applications of Fuzzy Sets Theory, LNCS, vol. 4578, pp. 195–202. Springer, Heidelberg (2007)
29.
Yao, A.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721–736 (1892)CrossRef
30.
Zahn, C.T.: Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans. Comput. C20, 68–86 (1971)CrossRef
Metadata
Title
Graph-Based Clustering Algorithms
Authors
Ágnes Vathy-Fogarassy
János Abonyi
Copyright Year
2013
Publisher
Springer London
Book
Graph-Based Clustering and Data Visualization Algorithms

Print ISBN: 978-1-4471-5157-9

Electronic ISBN: 978-1-4471-5158-6

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4471-5158-6_2

Premium Partner

    Image Credits