Search

Coarse-graining of complex networks is one of the important algorithms to study large-scale networks, which is committed to reducing the size of networks while preserving some topological information or dynamic properties of the original networks. Spectral coarse-graining (SCG) is one of the typical coarse-graining algorithms, which can keep the synchronization ability of the original network well. However, the calculation of SCG is large, which limits its real-world applications. And it is difficult to accurately control the scale of the coarse-grained network. In this paper, a new SCG algorithm based on K-means clustering (KCSCG) is proposed, which cannot only reduce the amount of calculation, but also accurately control the size of coarse-grained network. At the same time, KCSCG algorithm has better effect in keeping the network synchronization ability than SCG algorithm. A large number of numerical simulations and Kuramoto-model example on several typical networks verify the feasibility and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A fuzzy classifier using multiple ellipsoids to approximate decision regions for classification is designed in this paper. To learn the sizes and orientations of ellipsoids, an algorithm called evolutionary ellipsoidal classification algorithm (EECA) that integrates the genetic algorithm (GA) with the Gustafson-Kessel algorithm (GKA) is proposed. Within EECA the GA is employed to learn the size of every ellipsoid. With the size of every ellipsoid encoded and intelligently estimated in the GA chromosome, GKA is utilized to learn the corresponding ellipsoid. GKA is able to adapt the distance norm to the underlying distribution of the prototype data points for an assigned ellipsoid size. A process called directed initialization is proposed to improve EECA's learning efficiency. Because EECA learns the data point distribution in every cluster by adjusting an ellipsoid with suitable size and orientation, the information contained in the ellipsoid is further utilized to improve the cluster validity. A cluster validity measure based on the ratio of summation for each intra-cluster scatter with respect to the inter-cluster separation is defined in this paper. The proposed cluster validity measure takes advantage of EECA's learning capability and serves as an effective index for determining the adequate number of ellipsoids required for classification. [ABSTRACT FROM AUTHOR]

Community detection and analysis have attracted wide public concerns over the recent years. Meanwhile, many related algorithms in complex networks have been proposed. However, most of them concentrate on undirected and unweighted networks. Concerning the significant theoretical value and potential application foreground for directed-weighted networks, in this paper, a novel hierarchical communities detection algorithm (termed as DCBAI) has been proposed on the basis of asymmetric intimacy between nodes. Community structures are effectively detected by node clustering algorithm in directed-weighted network, and a set of optimal communities are generated. In addition, a new and asymmetric parameter is adopted to measure the intimate relationship between nodes. We make some simulation using the proposed algorithm in real-world networks and artificial networks, and the result obtained proves that the parameter can describe the direct and indirect relationships between two nodes. Eventually, comparison with similar algorithms shows that our proposed algorithm has better performance. [ABSTRACT FROM AUTHOR]

In this paper, we proposed a link density clustering (LDC) method for overlapping community detection based on density peaks. We firstly use an extended cosine link distance metric to reflect the relationship of links. Then we introduce a clustering algorithm with fast search for solving the link clustering (LC) problem by density peaks with box plot strategy to determine the cluster centers automatically. Finally, we acquire both the link communities and the node communities. Our algorithm is compared with other representative algorithms through substantial experiments on real-world networks. The experimental results show that our algorithm consistently outperforms other algorithms in terms of modularity and coverage. [ABSTRACT FROM AUTHOR]

Many clustering algorithms have been proposed in literature to identify the parameters involved in the Takagi-Sugeno fuzzy model, we can quote as an example the Fuzzy C-Means algorithm (FCM), the Possibilistic C-Means algorithm (PCM), the Allied Fuzzy C-Means algorithm (AFCM), the NEPCM algorithm and the KNEPCM algorithm. The main drawback of these algorithms is the sensitivity to initialization and the convergence to a local optimum of the objective function. In order to overcome these problems, the particle swarm optimization is proposed. Indeed, the particle swarm optimization is a global optimization technique. Thus, the incorporation of local research capacity of the KNEPCM algorithm and the global optimization ability of the PSO algorithm can solve these problems. In this paper, a new clustering algorithm called KNEPCM-PSO is proposed. This algorithm is a combination between Kernel New Extended Possibilistic C-Means algorithm (KNEPCM) and Particle Swarm Optimization (PSO). The effectiveness of this algorithm is tested on nonlinear systems and on an electro-hydraulic system. [ABSTRACT FROM AUTHOR]

Sharing data to a third party for the mutual benefit of the data owners plays a vital need in all computer applications. Ensuring the privacy of sensitive data is an important issue in data sharing and hence there is a need for privacy preserving data mining algorithms. Traditional privacy preserving algorithms are prone to attacks, have high information loss and sometimes fail to achieve the privacy constraints. In this paper, a (G,S) clustering algorithm is proposed to achieve clusters each with S diverse sensitive values for the sensitive attribute. The number of distinct sensitive values in each cluster would be exactly equal to the number of sensitive values in the given data set. The clusters' formed are anonymized by replacing the actual values with the centroid(G) of the cluster. The algorithm achieves the maximum possible diverse sensitive values in each cluster making it resilient to similarity attack. The method guarantees high degree of privacy with very minimal loss of information. The privacy degree of the clusters formed is at least equal to the number of distinct values in the sensitive attribute. The worst case linking probability would be as low as 0.5. The significance of this algorithm is its resilience to similarity attack. The performance of the algorithm is proved to be better than the existing algorithms in terms of KL Divergence, Discernibility metric and few other metrics. [ABSTRACT FROM AUTHOR]

Most of the existing privacy preserving clustering (PPC) algorithms do not consider the worst case privacy guarantees and are based on heuristic notions. In addition, these algorithms do not run efficiently in the case of high dimensionality of data. In this paper, to alleviate these challenges, we propose a new PPC algorithm, which is based on Daubechies-2 wavelet transform (D2WT) and preserves the differential privacy notion. Differential privacy is the strong notion of privacy, which provides the worst case privacy guarantees. On the other hand, most of the existing differential-based PPC algorithms generate data with poor utility. If we apply differential privacy properties over the original raw data, the resulting data will offer lower quality of clustering (QOC) during the clustering analysis. Therefore, we use D2WT for the preprocessing of the original data before adding noise to the data. By applying D2WT to the original data, the resulting data not only contains lower dimension compared to the original data, but also can provide differential privacy guarantee with high QOC due to less noise addition. The proposed algorithm has been implemented and experimented over some well-known datasets. We also compare the proposed algorithm with some recently introduced algorithms based on utility and privacy degrees. [ABSTRACT FROM AUTHOR]

Community detection is a fundamental work to analyze the structural and functional properties of complex networks. There are many algorithms proposed to find the optimal communities of network. In this paper, we focus on how vertex order influences the results of community detection. By using consensus clustering, we discover communities and get a consensus matrix under different vertex orders. Based on the consensus matrix, we study the phenomenon that some nodes are always allocated in the same community even with different vertex permutations. We call this group of nodes as constant community and propose a constant community detection algorithm (CCDA) to find constant communities in network. We also further study the internal properties of constant communities and find constant communities play a guiding role in community detection. Finally, a discussion of constant communities is given in the hope of being useful to others working in this field. [ABSTRACT FROM AUTHOR]

In this paper, formation of diverse groups of individuals based on attributes and two diversity measures are discussed. The formation of clusters in a diversity space is described. An algorithm is given for diverse clustering based on separation in the space and not the nearness using application based diversity thresholds and number of clusters. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel cosegmentation algorithm based on active contour model which utilizes local and global image statistics. Many localized region-based active contour models have been proposed to solve a challenging problem of the property (such as intensity, color, texture, etc.) inhomogeneities that often occurs in real images, but these models usually cannot reasonably evolve the curve in this situation that some center points along the curve are in homogeneous regions and their local regions are far away from the object. In order to overcome the difficulties we selectively enlarge the driven force of some points and introduce the edge indicator function to avoid the curve over-shrinking or over-expanding on the salient boundaries. In addition, we introduce global image statistics to better the curve evolution and try to avoid the given energy functional converging to a local minimum. Practical experiments show that our algorithm can obtain better segmentation results. [ABSTRACT FROM AUTHOR]

In this paper, a new classification method (ADCC) for high-dimensional data is proposed. In this method, a decision cluster classification (DCC) model consists of a set of disjoint decision clusters, each labeled with a dominant class that determines the class of new objects falling in the cluster. A cluster tree is first generated from a training data set by recursively calling a variable weighting k-means algorithm. Then, the DCC model is extracted from the tree. Various tests including Anderson-Darling test are used to determine the stopping condition of the tree growing. A series of experiments on both synthetic and real data sets have been conducted. Their results show that the new classification method (ADCC) performed better in accuracy and scalability than existing methods like k-NN, decision tree and SVM. ADCC is particularly suitable for large, high-dimensional data with many classes. [ABSTRACT FROM AUTHOR]

The increased demand for clustering objects of unlabeled data into similarity group lies in determining a number of clusters. In addition, the performance of the cluster should be analyzed to provide the precise clustering of objects. Available clustering algorithm depends on the number of clusters C to search with threshold. The proposed method of this paper is Enhanced Visual Assessment of Cluster Tendency, which robotically identifies the number of object groups or clusters in unlabeled datasets. The proposed algorithm relies on visual assessment of cluster tendency (VAT) that intermingles Euclidean, Mahalanobis distance measures, and common image processing techniques. Enhanced VAT produces a binary image, which can be visually assessed for the cluster tendency. However, VAT becomes disrupting for huge datasets. Enhanced VAT reduces the amount of computation and performs dissimilarities with different measures of metrics that are used for an effective visual evaluation process. Validation of our algorithm is performed on several UCI datasets and HIV real world datasets. [ABSTRACT FROM AUTHOR]

The clustering coefficient of user-object bipartite networks is presented to evaluate the overlap percentage of neighbors rating lists, which could be used to measure interest correlations among neighbor sets. The collaborative filtering (CF) information filtering algorithm evaluates a given user's interests in terms of his/her friends' opinions, which has become one of the most successful technologies for recommender systems. In this paper, different from the object clustering coefficient, users' clustering coefficients of user-object bipartite networks are introduced to improve the user similarity measurement. Numerical results for MovieLens and Netflix data sets show that users' clustering effects could enhance the algorithm performance. For MovieLens data set, the algorithmic accuracy, measured by the average ranking score, can be improved by 12.0% and the diversity could be improved by 18.2% and reach 0.649 when the recommendation list equals to 50. For Netflix data set, the accuracy could be improved by 14.5% at the optimal case and the popularity could be reduced by 13.4% comparing with the standard CF algorithm. Finally, we investigate the sparsity effect on the performance. This work indicates the user clustering coefficients is an effective factor to measure the user similarity, meanwhile statistical properties of user-object bipartite networks should be investigated to estimate users' tastes. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of learning to classify texts by exploiting information derived from clustering both training and testing sets. The incorporation of knowledge resulting from clustering into the feature space representation of the texts is expected to boost the performance of a classifier. We present an empirical study of the proposed algorithm on a variety of datasets. We attempt to answer various questions such as the effect of independence or relevance amongst features, the effect of the size of the training set and the effect of noise. The results are encouraging, revealing that information resulting from clustering can create text classifiers of high-accuracy. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance and the discrete Fréchet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the 'longest' subtrajectory cluster is as hard as MaxClique to compute and approximate. [ABSTRACT FROM AUTHOR]

Cluster ensemble has proved to be a good alternative when facing cluster analysis problems. It consists of generating a set of clusterings from the same dataset and combining them into a final clustering. The goal of this combination process is to improve the quality of individual data clusterings. Due to the increasing appearance of new methods, their promising results and the great number of applications, we consider that it is necessary to make a critical analysis of the existing techniques and future projections. This paper presents an overview of clustering ensemble methods that can be very useful for the community of clustering practitioners. The characteristics of several methods are discussed, which may help in the selection of the most appropriate one to solve a problem at hand. We also present a taxonomy of these techniques and illustrate some important applications. [ABSTRACT FROM AUTHOR]

Detecting outliers in high dimensional datasets is quite a difficult data mining task. Mining outliers in subspaces seems to be a promising solution, because outliers may be embedded in some interesting subspaces. Due to the existence of many irrelevant dimensions in high dimensional datasets, it is of great importance to eliminate the irrelevant or unimportant dimensions and identify outliers in interesting subspaces with strong correlation. Normally, the correlation among dimensions can be determined by traditional feature selection techniques and subspace-based clustering methods. The dimension-growth subspace clustering techniques find interesting subspaces in relatively lower possible dimension space, while dimension-growth approaches intend to find the maximum cliques in high dimensional datasets. This paper presents a novel approach by identifying outliers in correlated subspaces. The degree of correlation among dimensions is measured in terms of the mean squared residue. In doing so, we employ the frequent pattern algorithms to find the correlated subspaces. Based on the correlated subspaces obtained, outliers are distinguished from the projected subspaces by using classical outlier detection techniques. Empirical studies show that the proposed approach can identify outliers effectively in high dimensional datasets. [ABSTRACT FROM AUTHOR]

Breast cancer occurs in over 8% of women during their lifetime, and is the leading cause of death among women. Sonography is superior to mammography because it has the ability to detect focal abnormalities in the dense breasts and has no side-effect. In this paper, we propose a novel automatic segmentation algorithm based on the characteristics of breast tissue and eliminating particle swarm optimization (EPSO) clustering analysis. The characteristics of mammary gland in breast ultrasound (BUS) images are analyzed and utilized, and a method based on step-down threshold technique is employed to locate the mammary gland area. The EPSO clustering algorithm utilizes the idea of "survival of the superior and weeding out the inferior". The experimental results demonstrate that the proposed approach can segment BUS image with high accuracy and low computational time. The EPSO clustering method reduces the computational time by 32.75% compared with the standard PSO clustering algorithm. The proposed approach would find wide applications in automatic lesion classification and computer aided diagnosis (CAD) systems of breast cancer. [ABSTRACT FROM AUTHOR]

In many distributed modeling, control or information processing applications, clustering patterns that share certain similarities is the critical first step. However, many traditional clustering algorithms require centralized processing, reliable data collection and the availability of all the raw data in one place at one time. None of these requirement can be met in many complex real world problems. In this paper, we present an agent-based method for combining multiple base clusterings into a single unified "consensus" clustering that is robust against many types of failures and does not require spatial/temporal synchronization. In this approach, agents process clusterings coming from separate sources and pool them to produce a unified consensus. The first contribution of this work is to provide an adaptive method by which the agents update their selections to maximize an objective function based on the quality of the consensus clustering. The second contribution of this work is in providing intermediate agent-specific objective functions that significantly improve the quality of the consensus clustering process. Our results show that this agent-based method achieves comparable or better performance than traditional non-agent consensus clustering methods in fault-free conditions, and remains effective under a wide range of failure scenarios that paralyze the traditional methods. [ABSTRACT FROM AUTHOR]

Identifying communities in complex networks has recently attracted considerable attention in different fields. The goal of community identification is to cluster vertices of a network into groups, which is the same as clustering in machine learning and data mining domains. A recent proposed clustering method called affinity propagation shows high performance in clustering data sets into groups, and it does not require that the number of clusters be pre-specified. In this paper, based on a new method for calculating similarity between pairs of vertices and a transforming method for a given similarity from likelihood to log-domain, we apply that affinity propagation clustering method to identify communities in complex networks. Extensive simulation results demonstrate that affinity propagation clustering algorithm is very effective for identifying community structures in both computer-generated and real-world network data. [ABSTRACT FROM AUTHOR]

This paper proposes a hybrid approach to image registration for inferring the affine transformation that best matches a pair of partially overlapping aerial images. The image registration is formulated as a two-stage hybrid approach combining both phase correlation method (PCME) and optical flow equation (OFE) based estimation algorithm in a coarse-to-fine manner. With PCME applied at the highest level of decomposition, the initial affine parameter model could be first estimated. Subsequently, the OFE-based estimation algorithm is incorporated into the proposed hybrid approach using a multi-resolution mechanism. PCME is characterized by its insensitivity to large geometric transform between images, which can effectively guide the OFE-based registration. For image pairs under salient brightness variations, we propose a nonlinear image representation that emphasizes common intensity information, suppresses the non-common information between an image pair, and is suitable for the proposed coarse-to-fine hierarchical iterative processing. Experimental results demonstrate the accuracy and efficiency of our proposed approach using different types of aerial images. [ABSTRACT FROM AUTHOR]

In this paper, the combination of unsupervised clustering algorithms with feedforward neural networks in exchange rate time series forecasting is studied. Unsupervised clustering algorithms have the desirable property of deciding on the number of partitions required to accurately segment the input space during the clustering process, thus relieving the user from making this ad hoc choice. Combining this input space partitioning methodology with feedforward neural networks acting as local predictors for each identified cluster helps alleviate the problem of nonstationarity frequently encountered in real-life applications. An improvement in the one-step-ahead forecasting accuracy was achieved compared to a global feedforward neural network model for the time series of the exchange rate of the German Mark to the US Dollar. [ABSTRACT FROM AUTHOR]

Clustering can be defined as the process of "grouping" a collection of objects into subsets or clusters. The clustering problem has been addressed in numerous contexts and by researchers in different disciplines. This reflects its broad appeal and usefulness as an exploratory data analysis approach. Unsupervised clustering algorithms have been developed to address real world problems in which the number of clusters present in the dataset is unknown. These algorithms approximate the number of clusters while performing the clustering procedure. This paper is a first step towards the development of unsupervised clustering algorithms capable of identifying clusters within clusters. To this end, an unsupervised clustering algorithm is modified so as to take into consideration the fractal dimension of the data. The experimental results indicate that this approach can provide further qualitative information compared to the unsupervised clustering algorithm. [ABSTRACT FROM AUTHOR]

The problem of outlier and change-point identification has received considerable attention in traditional linear regression models from both, classical and Bayesian standpoints. In contrast, for the case of regression models with measurement errors, also known as error-in-variables models, the corresponding literature is scarce and largely focused on classical solutions for the normal case. The main object of this paper is to propose clustering algorithms for outlier detection and change-point identification in scale mixture of error-in-variables models. We propose an approach based on product partition models (PPMs) which allows one to study clustering for the models under consideration. This includes the change-point problem and outlier detection as special cases. The outlier identification problem is approached by adapting the algorithms developed by Quintana and Iglesias [32] for simple linear regression models. A special algorithm is developed for the change-point problem which can be applied in a more general setup. The methods are illustrated with two applications: (i) outlier identification in a problem involving the relationship between two methods for measuring serum kanamycin in blood samples from babies, and (ii) change-point identification in the relationship between the monthly dollar volume of sales on the Boston Stock Exchange and the combined monthly dollar volumes for the New York and American Stock Exchanges. [ABSTRACT FROM AUTHOR]

While the task scheduling problem under the delay model has been studied extensively, relatively little research exists for more realistic communication models such as the Log P model which considers, in addition to latency, the cost of sending and receiving messages, and the network or link capacity. The task scheduling problem is known to be NP-complete even under the delay model (a special case of the Log P model). This paper investigates the similarities and differences between task-clustering algorithms for the delay and Log P models, and describes a task-scheduling algorithm for the allocation of arbitrary task graphs to fully connected networks of processors under the Log P model. The strategy exploits the replication and clustering of tasks to minimize the ill effects of communication overhead on the makespan. A number of restrictions are presented which are used to simplify the design of the new algorithm. The quality of the schedules produced by the algorithm compare favorably with two well-known delay model-based algorithms and a previously existing Log P strategy. [ABSTRACT FROM AUTHOR]