Swipe to navigate through the chapters of this book
This chapter is devoted to clustering similarity, graph and network data – these are represented by square matrices rather than rectangular ones. This chapter describes methods for finding a cluster or two-cluster split combining three types of approaches from both old and recent developments: (a)combinatorial approach that is oriented at clustering as optimization of some reasonable measure of cluster homogeneity, (b)additive clustering approach that is based on a data recovery model at which the data is decoded from a cluster structure to be found by minimizing the discrepancy between them and observed similarities, and (c)spectral clustering approach exploiting the machinery of matrix eigenvalues and eigenvectors as a relaxation of combinatorial problems for similarity clustering.
Please log in to get access to this content
To get access to this content you need the following product:
Johnsonbaugh, R., Schaefer, M.: Algorithms. Pearson Prentice Hall, Upper Saddle River (2004). ISBN 0-13-122853-6.
Mirkin, B.: Mathematical Classification and Clustering. Kluwer Academic Press, Boston-Dordrecht (1996).
Mirkin, B., Camargo, R., Fenner, T., Loizou, G., Kellam, P.: Similarity clustering of proteins using substantive knowledge and reconstruction of evolutionary gene histories in herpesvirus. Theor. Chem. Acc.: Theory, Comput. Mod. 125(3–6), 569–582 (2010). CrossRef
Newman, M.E.J.: Modularity and community structure in networks. PNAS. 103(23), 8577–8582 (2006). CrossRef
Newman, M., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E. 69, 026113 (2004). CrossRef
Shepard, R.N., Arabie, P.: Additive clustering: Representation of similarities as combinations of discrete overlapping properties. Psychol. Rev. 86, 87–123 (1979). CrossRef
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Machine Intelligence. 22(8), 888–905 (2000). CrossRef
- Approximate and Spectral Clustering for Network and Affinity Data
- Springer London
- Sequence number
- Chapter number
- Chapter 8