SAcluster
swMATH ID:  6867 
Software Authors:  Cheng, Hong; Zhou, Yang; Huang, Xin; Yu, Jeffrey Xu 
Description:  Clustering large attributed information networks: an efficient incremental computing approach In recent years, many information networks have become available for analysis, including social networks, road networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SAcluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SACluster performs matrix multiplication to calculate the random walk distances between graph vertices. As part of the clustering refinement, the graph edge weights are iteratively adjusted to balance the relative importance between structural and attribute similarities. As a consequence, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SAcluster, in this paper, we propose an efficient algorithm IncCluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost IncCluster can save. We further design parallel matrix computation techniques on a multicore architecture. Experimental results demonstrate that IncCluster achieves significant speedup over SACluster on large graphs, while achieving exactly the same clustering quality in terms of intracluster structural cohesiveness and attribute value homogeneity. 
Homepage:  http://www.mendeley.com/catalog/clusteringlargeattributedgraphsefficientincrementalapproach/ 
Keywords:  graph clustering; vertex partitioning; vertex properties; incremental computation; parallel computing; SAcluster; structural and attribute similarities; random walk distances; clustering refinement; edge weights 
Related Software:  Inccluster; Pajek; SimRank; LINE; apcluster; node2vec; GraRep; AS 136; APCluster; SNAP; GitHub; DAVID; AppliedPredictiveModeling; igraph; GenLouvain; CRIO; Graclus; gSkeletonClu; GraphScope 
Cited in:  11 Documents 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Clustering large attributed information networks: an efficient incremental computing approach. Zbl 1259.05150 Cheng, Hong; Zhou, Yang; Huang, Xin; Yu, Jeffrey Xu 
2012

all
top 5
Cited by 28 Authors
all
top 5
Cited in 8 Serials
all
top 5