Affordable Access

Access to the full text

A unified agent-based framework for constrained graph partitioning

Authors
  • Ntaflos, Lefteris
  • Trimponias, George
  • Papadias, Dimitris
Type
Published Article
Journal
The VLDB Journal
Publisher
Springer Berlin Heidelberg
Publication Date
Oct 27, 2018
Volume
28
Issue
2
Pages
221–241
Identifiers
DOI: 10.1007/s00778-018-0526-5
Source
Springer Nature
Keywords
License
Yellow

Abstract

Social networks offer various services such as recommendations of social events, or delivery of targeted advertising material to certain users. In this work, we focus on a specific type of services modeled as constrained graph partitioning (CGP). CGP assigns users of a social network to a set of classes with bounded capacities so that the similarity and the social costs are minimized. The similarity cost is proportional to the dissimilarity between a user and his class, whereas the social cost is measured in terms of friends that are assigned to different classes. In this work, we investigate two solutions for CGP. The first utilizes a game-theoretic framework, where each user constitutes a player that wishes to minimize his own social and similarity cost. The second employs local search, and aims at minimizing the global cost. We show that the two approaches can be unified under a common agent-based framework that allows for two types of deviations. In a unilateral deviation, an agent switches to a new class, whereas in a bilateral deviation a pair of agents exchange their classes. We develop a number of optimization techniques to improve result quality and facilitate efficiency. Our experimental evaluation on real datasets demonstrates that the proposed methods always outperform the state of the art in terms of solution quality, while they are up to an order of magnitude faster.

Report this publication

Statistics

Seen <100 times