重叠聚类和属性图聚类算法分析.docx

Abstract
In real life, many objects could be modeled in the form of graph data, and there are many application values using data mining algorithms on graph data. Clustering is an important method in data mining process. Many researchers have proposed many graph clustering algorithms to solve this problem. In this paper, the writer proposes two improved algorithms to solve two problem better, which appear in many problem in clustering graph data.
Traditional clustering could find many different clusters, each pairs of which could not overlap. This conflicts the real life seriously. For example, every person belongs to many munities in work. Therefore, we should allow some vertices belong to munities, and we call this problem "munity detection". Edge-based algorithms could solve this problem and find munity structure. In this paper, a novel edge-based algorithms is proposed. In this algorithms, every edge in the graph is converted into multi-edges, and we use overlapping methods to find edge-based clusters, then convert the result into vertex-based clusters. Tests on real data give good result.
Graph can contains not only topology structure, but also node/edge attributes, which is called attribute graph. Attribute graph could describe this world better, and data mining on attribute graphs could find more accurate or more interesting patterns. In this paper, we could get the weight of every edge, according to node attributes. We propose a simple and useful methods to determining the edge weights, then using weighted graph clustering algorithms to cluster the attribute graph. Attribute weight matrix could be calculated using EM algorithms. Tests indicate that the methods proposed can find better clusters than the newest algorithms.
Keywords: overlapping munity detection;edge-based clustering; attribute graph;weight
目录
摘要…………………………………………………………………………………Ⅰ Abstract……………………………………………………………………………Ⅱ第一章绪论…………………………………………………………………………1
课题背景………………………………………………………………………1
1