Clustering is a classical research field due to its broad applications in data mining such as emotion detection, event extraction and topic discovery. It aims to discover intrinsic patterns which can be formed as clusters from a collection of data. Significant progress have been made by the Density-based Spatial Clustering of Applications with Noise (DBSCAN) and its variants. However, there is a major limitation that current density-based algorithms suffer from linear connection problem, where they perform poorly to discriminate objective clusters which are “connected” by a few data points. Moreover, the parameter setting and the time cost make it hard to be well-adapted in massive data analysis. To address these problems, we propose a novel adaptive density-based spatial clustering algorithm called Ada-DBSCAN, which consists of a data block splitter and a data block merger, coordinated by local clustering and global clustering. We conduct extensive experiments on both artificial and real-world datasets to evaluate the effectiveness of Ada-DBSCAN. Experimental results show that our algorithm evidently outperforms several strong baselines in both clustering accuracy and human evaluation. Besides, Ada-DBSCAN shows significant improvement of efficiency compared with DBSCAN.
Online social networks (OSNs) have received a lot of attentions recently since they provide a new platform for product promotion and online viral marketing. Influence maximization problem has been extensively studied on some existing influence diffusion models in number of domains. However, most of the existing studies consider OSNs as friendly networks only containing friendship relationships, whereas the hostile relations do exist in many OSNs in real life, e.g., Epinions and Slashdot. In this paper, we integrate the PageRank on signed social networks and use the integrated PageRank to study influence maximization in OSNs with both friend and hostile relations which are respected as positive edges and negative edges on signed networks. In addition, we use the extended vote model to study the influence diffusion on signed networks. We then conducted comprehensive experiments on real social networks to select initial k seeds for influence maximization, and results indicate that our integrated PageRank method performs better than other heuristic algorithms.
Contact detection is a general problem of many physical simulations. This work presents a multigrid method for general contact detection problems (MGCD). The multigrid idea is integrated with contact detection problems. Both the time complexity and memory consumption of the MGCD are . Unlike other methods, whose efficiencies are influenced strongly by the object size distribution, the performance of MGCD is insensitive to the object size distribution. We compare the MGCD with the no binary search (NBS) method and the multilevel boxing method in three dimensions for both time complexity and memory consumption. For objects with similar size, the MGCD is as good as the NBS method, both of which outperform the multilevel boxing method regarding memory consumption. For objects with diverse size, the MGCD outperform both the NBS method and the multilevel boxing method. We use the MGCD to solve the contact detection problem for a granular simulation system based on the discrete element method. From this granular simulation, we get the density property of monosize packing and binary packing with size ratio equal to 10. The packing density for monosize particles is 0.636. For binary packing with size ratio equal to 10, when the number of small particles is 300 times as the number of big particles, the maximal packing density 0.824 is achieved.