NDLI: Exploiting small world property for network clustering

Please wait, while we are loading the content...

Exploiting small world property for network clustering

Content Provider	Springer Nature Link
Author	Qian, Tieyun Li, Qing Srivastava, Jaideep Peng, Zhiyong Yang, Yang Wang, Shuo
Copyright Year	2013
Abstract	Graph partitioning is a traditional problem with many applications and a number of high-quality algorithms have been developed. Recently, demand for social network analysis arouses the new research interest on graph partitioning/clustering. Social networks differ from conventional graphs in that they exhibit some key properties like power-law and small-world property. Currently, these features are largely neglected in popular partitioning algorithms. In this paper, we present a novel framework which leverages the small-world property for finding clusters in social networks. The framework consists of several key features. Firstly, we define a total order, which combines the edge weight, the small-world weight, and the hub value, to better reflect the connection strength between two vertices. Secondly, we design a strategy using this ordered list, to greedily, yet effectively, refine existing partitioning algorithms for common objective functions. Thirdly, the proposed method is independent of the original approach, such that it could be integrated with any types of existing graph clustering algorithms. We conduct an extensive performance study on both real-life and synthetic datasets. The empirical results clearly demonstrate that our framework significantly improves the output of the state-of-the-art methods. Furthermore, we show that the proposed method returns clusters with both internal and external higher qualities.
Starting Page	405
Ending Page	425
Page Count	21
File Format	PDF
ISSN	1386145X
Journal	World Wide Web
Volume Number	17
Issue Number	3
e-ISSN	15731413
Language	English
Publisher	Springer US
Publisher Date	2013-03-29
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	graph partitioning, small world property, network clustering Information Systems Applications (incl. Internet) Database Management Operating Systems
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Software Hardware and Architecture

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

Discovering small-world in association link networks for association learning

Indexing dataspaces with partitions

Efficient processing of graph similarity search

Privacy preserving graph publication in a distributed environment

Multidimensional networks: foundations of structural analysis

Probabilistic Web Data Management

SocialSearch $^{ + }$: enriching social network with web evidences

Graffiti: graph-based classification in heterogeneous networks

Bursty event detection from collaborative tags

Exploiting small world property for network clustering

Similar Documents

Discovering small-world in association link networks for association learning

Indexing dataspaces with partitions

Efficient processing of graph similarity search

Privacy preserving graph publication in a distributed environment

Multidimensional networks: foundations of structural analysis

Probabilistic Web Data Management

SocialSearch $^{ + }$: enriching social network with web evidences

Graffiti: graph-based classification in heterogeneous networks

Bursty event detection from collaborative tags

Exploiting small world property for network clustering