Access Restriction

Author Rossi, Ryan A. ♦ Ahmed, Nesreen K.
Source SpringerLink
Content type Text
Publisher Springer Vienna
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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
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.
ISSN 18695450
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-09-12
Publisher Place Vienna
e-ISSN 18695469
Journal Social Network Analysis and Mining
Volume Number 4
Issue Number 1
Page Count 37
Starting Page 1
Ending Page 37

Open content in new tab

   Open content in new tab
Source: SpringerLink