NDLI: Coloring large complex networks

Content Provider	SpringerLink
Author	Rossi, Ryan A. Ahmed, Nesreen K.
Copyright Year	2014
Abstract	Given a large social or information network, how can we partition the vertices into sets (i.e., colors) such that no two vertices linked by an edge are in the same set while minimizing the number of sets used. Despite the obvious practical importance of graph coloring, existing works have not systematically investigated or designed methods for large complex networks. In this work, we develop a unified framework for coloring large complex networks that consists of two main coloring variants that effectively balances the tradeoff between accuracy and efficiency. Using this framework as a fundamental basis, we propose coloring methods designed for the scale and structure of complex networks. In particular, the methods leverage triangles, triangle-cores, and other egonet properties and their combinations. We systematically compare the proposed methods across a wide range of networks (e.g., social, web, biological networks) and find a significant improvement over previous approaches in nearly all cases. Additionally, the solutions obtained are nearly optimal and sometimes provably optimal for certain classes of graphs (e.g., collaboration networks). We also propose a parallel algorithm for the problem of coloring neighborhood subgraphs and make several key observations. Overall, the coloring methods are shown to be (1) accurate with solutions close to optimal, (2) fast and scalable for large networks, and (3) flexible for use in a variety of applications.
Starting Page	1
Ending Page	37
Page Count	37
File Format	PDF
ISSN	18695450
Journal	Social Network Analysis and Mining
Volume Number	4
Issue Number	1
e-ISSN	18695469
Language	English
Publisher	Springer Vienna
Publisher Date	2014-09-12
Publisher Place	Vienna
Access Restriction	Subscribed
Subject Keyword	Network coloring Unified framework Greedy methods Neighborhood coloring Triangle-core ordering Social networks Data Mining and Knowledge Discovery Complex Networks Game Theory, Economics, Social and Behav. Sciences Statistics for Social Science, Behavorial Science, Education, Public Policy, and Law Methodology of the Social Sciences
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications Media Technology Human-Computer Interaction Information Systems Communication

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 Libarray 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

The maximum imputation framework for neighborhood-based collaborative filtering

Mining and generating large-scaled social networks via MapReduce

Social media and political communication: a social media analytics framework

Social system as complex networks

Evaluation framework for social media brand presence

Social media analysis and summarization for opinion mining: a business case study

SPADE: a social-spam analytics and detection framework

Clustering memes in social media streams

User similarities on social networks

Coloring large complex networks

Similar Documents

The maximum imputation framework for neighborhood-based collaborative filtering

Mining and generating large-scaled social networks via MapReduce

Social media and political communication: a social media analytics framework

Social system as complex networks

Evaluation framework for social media brand presence

Social media analysis and summarization for opinion mining: a business case study

SPADE: a social-spam analytics and detection framework

Clustering memes in social media streams

User similarities on social networks

Coloring large complex networks