Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 4

degree Related Publications

4 A Minimum Spanning Tree-Based Method for Initializing the K-Means Clustering Algorithm

Authors: X. Zhang, J. Yang, Y. Ma, S. Li, Y. Zhang

Abstract:

The traditional k-means algorithm has been widely used as a simple and efficient clustering method. However, the algorithm often converges to local minima for the reason that it is sensitive to the initial cluster centers. In this paper, an algorithm for selecting initial cluster centers on the basis of minimum spanning tree (MST) is presented. The set of vertices in MST with same degree are regarded as a whole which is used to find the skeleton data points. Furthermore, a distance measure between the skeleton data points with consideration of degree and Euclidean distance is presented. Finally, MST-based initialization method for the k-means algorithm is presented, and the corresponding time complexity is analyzed as well. The presented algorithm is tested on five data sets from the UCI Machine Learning Repository. The experimental results illustrate the effectiveness of the presented algorithm compared to three existing initialization methods.

Keywords: minimum spanning tree, degree, k-means, initial cluster center

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 892
3 Eccentric Connectivity Index, First and Second Zagreb Indices of Corona Graph

Authors: A. Kulandai Therese

Abstract:

The eccentric connectivity index based on degree and eccentricity of the vertices of a graph is a widely used graph invariant in mathematics. In this paper, we present the explicit eccentric connectivity index, first and second Zagreb indices for a Corona graph and sub divisionrelated corona graphs.

Keywords: corona graph, degree, eccentricity, first zagreb index, Eccentric Connectivity Index, Second Zagreb index and Subdivision graphs

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1753
2 Terminal Wiener Index for Graph Structures

Authors: J. Baskar Babujee, J. Senbagamalar

Abstract:

The topological distance between a pair of vertices i and j, which is denoted by d(vi, vj), is the number of edges of the shortest path joining i and j. The Wiener index W(G) is the sum of distances between all pairs of vertices of a graph G. W(G) = i

Keywords: Distance, tree, graph, degree, wiener index, Pendent vertex

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1727
1 Topological Properties of an Exponential Random Geometric Graph Process

Authors: Yilun Shang

Abstract:

In this paper we consider a one-dimensional random geometric graph process with the inter-nodal gaps evolving according to an exponential AR(1) process. The transition probability matrix and stationary distribution are derived for the Markov chains concerning connectivity and the number of components. We analyze the algorithm for hitting time regarding disconnectivity. In addition to dynamical properties, we also study topological properties for static snapshots. We obtain the degree distributions as well as asymptotic precise bounds and strong law of large numbers for connectivity threshold distance and the largest nearest neighbor distance amongst others. Both exact results and limit theorems are provided in this paper.

Keywords: Wireless Network, Connectivity, autoregressive process, markovian, degree, random geometric graph

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1112