Real-Time Multi-Criteria Social Graph Partitioning
Authors:
Open Access
- 27 May 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1617-1628
Abstract
Graph partitioning has attracted considerable attention due to its high practicality for real-world applications. It is particularly relevant to social networks because it enables the grouping of users into communities for market analysis and advertising purposes. In this paper, we introduce RMGP, a type of real-time multi-criteria graph partitioning for social networks that groups the users based on their connectivity and their similarity to a set of input classes. We consider RMGP as an on-line task, which may be frequently performed for different query parameters (e.g., classes). In order to overcome the serious performance issues associated with the large social graphs found in practice, we develop solutions based on a game theoretic framework. Specifically, we consider each user as a player, whose goal is to find the class that optimizes his objective function. We propose algorithms based on best-response dynamics, analyze their properties, and show their efficiency and effectiveness on real datasets under centralized and decentralized scenarios.Keywords
Funding Information
- National Science Foundation (IIS-1115153, IIS-1320149, and CNS-1461963)
- Research Grants Council, University Grants Committee, Hong Kong (GRF-16207914)
This publication has 24 references indexed in Scilit:
- On social event organization2014
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- LARS: A Location-Aware Recommender System2012
- Graph Implementations for Nonsmooth Convex Programs2007
- Sampling from large graphs2006
- On the complexity of distributed graph coloring2006
- A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual techniqueACM Journal of Experimental Algorithmics, 2005
- Approximation algorithms for classification problems with pairwise relationshipsJournal of the ACM, 2002
- Multi-objective circuit partitioning for cutsize and path-based delay minimization2006 IEEE/ACM International Conference on Computer Aided Design, 2002
- Minimum cost spanning tree gamesMathematical Programming, 1981