A tripartite graph is three bipartite graphs between three vertex classes. In applications, it is three binary relationships between three sets of entities. The abundance of triangles in an otherwise sparse tripartite graph indicates that it is far from random and there are dense spots or clusters worth illuminating. Triangles in a tripartite graph form a graph by sharing edges. This triangle graph has some specific properties that make its clustering quite different from general graph clustering. In this work, we describe mode seeking in the triangle graph, based on a number of reasonable local density measures. Many of the properties and strategies for tripartite graphs described in this work extend to k-partite graphs including bipartite graphs.

The k-core of a graph is the maximal subgraph with minimum vertex degree k. When the core with the largest k is found, it can be removed and the next core can be found. In each of these cores (or shells), connected components have been enumerated in an existing graph clustering method. Here we propose a method to find graph clusters that are not just k-cores but also made of r-cliques. Just like the existing k-core clustering approach, our approach is also based on vertex and edge removals that can be made completely using local information (within the neighborhood). Our local and recursive algorithms are based on new graph theoretical insights that relate concepts including neighborhood, clique percolation, and k-core. We demonstrate our method with a gene network from PubMed data and compare our results with that from the existing k-core approach and use MeSH and TF-IDF ranking to show the differences in subject enrichment our approach can make.

The convergence and ordering of Kohonen's batch-mode self-organizing map with Heskes and Kappen's (1993) winner selection are proved. Selim and Ismail's (1984) objective function for k-means clustering is generalized in the convergence proof of the self-organizing map. It is shown that when the neighborhood relation is doubly decreasing, order in the map is preserved. An unordered map becomes ordered when a degenerate state of ordering is entered, where the number of distinct winners is one or two. One strategy to enter this state is to run the algorithm with a broad neighborhood relation.

Mean shift, a simple interactive procedure that shifts each data point to the average of data points in its neighborhood is generalized and analyzed in the paper. This generalization makes some k-means like clustering algorithms its special cases. It is shown that mean shift is a mode-seeking process on the surface constructed with a "shadow" kernal. For Gaussian kernels, mean shift is a gradient mapping. Convergence is studied for mean shift iterations. Cluster analysis if treated as a deterministic problem of finding a fixed point of mean shift that characterizes the data. Applications in clustering and Hough transform are demonstrated. Mean shift is also considered as an evolutionary strategy that performs multistart global optimization.>

No abstract available.

Associative evidential reasoning is the mechanism of combining evidence and evaluating hypotheses, which is the core of many computational systems. It is shown that under the generalized symmetry condition, that is, f(a,b)=neg (f(neg(a), neg(b))), where f is the combination operator satisfying common requirements like associativity and monotonicity, and neg maps positive elements to negative ones and vice versa, f is uniquely determined by a one-place mapping from the positive region to the set of positive reals. Furthermore, such combination formulas cannot be made robust, and quantizing the region will cause the loss of associativity or other inconsistencies. The implications on evidential reasoning system are: there exists often only one kind of formula for combining evidence; the quest for robust combination is often infeasible; and the attempt of converting numerical degrees of belief to linguistic quantifiers and vice versa is destined to be fruitless.>

Knowledge organization is a very important step in building an expert system. The problem is how to organize knowledge into a conceptual structure and thus make it complete, concise, and consistent. In this paper, concepts used in knowledge description are divided into tangible ones and intermediate ones depending on whether or not they appear in the input or the output of the system. Intermediate concepts and their relationships with tangible concepts are subjected to changes. A distance measure for rules and an algorithm for conceptual clustering are described. New intermediate concepts are generated using this algorithm. A few new concepts may replace a large number of old relationships and also generate new rules for the system. An experiment on traditional Chinese medicine shows that the proposed method produces results similar to those generated by experts.