NDLI: Clustering Large Attributed Graphs: An Efficient Incremental Approach

Content Provider	IEEE Xplore Digital Library
Author	Yang Zhou Hong Cheng Yu, J.X.
Copyright Year	2010
Abstract	In recent years, many networks have become available for analysis, including social 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, SA-Cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As the edge weights are iteratively adjusted to balance the importance between structural and attribute similarities, 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 SA-Cluster, in this paper, we propose an efficient algorithm Inc-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.
Starting Page	689
Ending Page	698
File Size	339861
Page Count	10
File Format	PDF
ISBN	9781424491315
ISSN	15504786
DOI	10.1109/ICDM.2010.41
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-12-13
Publisher Place	Australia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Clustering algorithms Matrix decomposition Complexity theory Partitioning algorithms Social network services Communities Gallium incremental computation graph clustering
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Clustering Large Attributed Graphs: An Efficient Incremental Approach (2010)

Split-node on overlapping community in dense social networks

Information integration for detecting communities in attributed graphs

Fraud Detection on Large Scale Social Networks

An Approach for the Blockmodeling in Multi-Relational Networks

Graph summarization for attributed graphs

Finding compact communities in large graphs

A computational geometric approach for overlapping community (cover) detection in social network

Community detection using a neighborhood strength driven Label Propagation Algorithm

Clustering Large Attributed Graphs: An Efficient Incremental Approach

Similar Documents

Clustering Large Attributed Graphs: An Efficient Incremental Approach (2010)

Split-node on overlapping community in dense social networks

Information integration for detecting communities in attributed graphs

Fraud Detection on Large Scale Social Networks

An Approach for the Blockmodeling in Multi-Relational Networks

Graph summarization for attributed graphs

Finding compact communities in large graphs

A computational geometric approach for overlapping community (cover) detection in social network

Community detection using a neighborhood strength driven Label Propagation Algorithm

Clustering Large Attributed Graphs: An Efficient Incremental Approach