• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>The VLDB journal >A unified agent-based framework for constrained graph partitioning
【24h】

A unified agent-based framework for constrained graph partitioning

机译：基于统一代理的约束图分区框架

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：社交网络提供各种服务，例如社交活动的推荐或将定向广告材料交付给某些用户。在这项工作中，我们专注于建模为约束图分区（CGP）的特定类型的服务。 CGP将社交网络的用户分配给具有有限能力的一组类别，以使相似性和社交成本最小化。相似度成本与用户与其班级之间的差异成正比，而社会成本则根据分配给不同班级的朋友来衡量。在这项工作中，我们研究了CGP的两种解决方案。第一种利用游戏理论框架，其中每个用户组成一个希望将自己的社交和相似性成本降至最低的玩家。第二种方法是使用本地搜索，旨在最大程度地降低全球成本。我们表明，可以在允许两种类型偏差的基于通用代理的框架下将这两种方法统一起来。在单方面偏差中，一个业务代表切换到新类别，而在双边偏差中，一对代理交换他们的类别。我们开发了许多优化技术来提高结果质量并提高效率。我们对真实数据集的实验评估表明，在解决方案质量方面，所提出的方法始终优于最新技术，尽管它们的速度要快一个数量级。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号