China
Africa
Explore chapters and articles related to this topic
Rough-fuzzy Clustering
Published in Sankar K. Pal, Pabitra Mitra, Pattern Recognition Algorithms for Data Mining, 2004
Clustering algorithms are often based on (a) iterative refinement of cluster parameters by optimizing some criterion function or likelihood of some probabilistic model (e.g., k-means [238], mixture of Gaussians [53]), or (b) graph theoretic techniques, where each cluster represents a subgraph of a graph of the entire data. One of the well-known graph theoretic clustering is based on the construction of the minimal spanning tree (MST) of the data [290]. Both the clustering approaches, iterative and graph-theoretic, have their advantages and disadvantages and cannot directly be applied for data mining. While the iterative refinement schemes like k-means and expectation maximization (EM) are fast and easily scalable to large databases [29], they can produce only convex clusters and are sensitive to initialization of the parameters. The graph-theoretic methods can model arbitrary shaped clusters but are slow and sensitive to noise. It may be noted that the advantages of one are complementary in overcoming the limitations of the other, and vice versa.
Graph Edit Distance—Theory, Algorithms, and Applications
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
The concepts of maximum common subgraph and minimum common supergraph can be used to measure the similarity of two graphs. The basic idea is the intuitive observation that the larger the common part of two graphs is, the higher their similarity. In the following, several distance measures between graphs based on the concepts of the MACS and the MICS will be presented.
On lower bounds for optimal Jacobian accumulation
Published in Optimization Methods and Software, 2018
The complexity of Algorithm 2 depends on the complexity of building a subgraph of G without the edge and the costs of determining the size of the sets and . To build the subgraph, we need to remove the edge and then recursively remove all intermediate vertices that have no incoming or no outgoing edges. The removal of each vertex also reduces the number of edges in the graph by at least one, such that we do not have to estimate the critical degree for this edge anymore. Therefore we assume that constructing a subgraph we need to remove only one edge. The costs of determining the sizes of and strongly depend on the given implementation. Discussing all various approaches goes beyond the scope of this paper. Thus we assume that F is the complexity of computing the size of and . For each removed edge, we need to estimate the sets and , hence Algorithm 2 has a worst-case complexity of .
Cooperative reference frame estimation for multi-agent systems via formation control
Published in Advanced Robotics, 2023
Consider an undirected graph with a node set and an edge set . The neighbor set of node i is denoted as Note that includes node i itself. For a node subset , the subgraph is the induced subgraph of with the node set and the edge set consisting of all of the edges in that contains the pairs of the nodes in . A node subset is called a clique if the induced subgraph is complete. A clique is said to be maximal clique if is contained by no other cliques. Let us consider the graph in Figure 2. The induced graph is complete, which implies is a clique. On the other hand, is incomplete, which implies is not a clique.
On finite-time and fixed-time consensus algorithms for dynamic networks switching among disconnected digraphs
Published in International Journal of Control, 2020
David Gómez-Gutiérrez, Carlos Renato Vázquez, Sergej Čelikovský, Juan Diego Sánchez-Torres, Javier Ruiz-León
A path from i to j in a digraph is a sequence of edges ··· starting in node i and ending in node j. A digraph is said to be connected if for every pair of vertices either there is a path from i to j or a path from j to i, otherwise it is said to be disconnected. A subgraph of is a graph such that and . A subgraph such that or is called a proper subgraph of . A subgraph of is called an induced subgraph if for any two vertices , there is an edge if and only if . An induced subgraph of that is connected is called maximal if it is not a proper subgraph of another connected subgraph of . A connected induced subgraph of that is maximal is called a connected component of . The edge connectivity of is the minimum number of edges that are needed to be removed to decrease the number of connected components.