GLEAM:基于潜在游戏优化的大型社交网络图聚类框架

随着在线社交网络的爆炸式增长,大规模图聚类的研究引起了极大的兴趣。 大多数传统方法将图聚类问题视为基于给定目标函数的优化问题。 但是,关于通过现实生活网络出现集群的方法论理论很少。 在本文中,在线社交网络中的每个演员都被视为非合作游戏中的自私玩家。 与每个节点关联的策略被定义为集群成员向量,并且每个人的动机是通过采用最合适的策略来最大化自己的社会身份。 在我们的游戏模型中,效用函数的定义受到了顺应性心理学的启发,顺应性心理学被定义为一个人通过参与不同群体而获得的社会身份的加权平均值。 通过此设置,建议的游戏可以很好地匹配潜在的游戏。 这样,可以由那些在纳什均衡中采用相同策略的紧密交互用户的行为来塑造集群。 为此,我们提出了一种基于potEntial gAme优化(GLEAM)的新颖的图聚类框架,用于并行图聚类。 它首先利用余弦相似度对原始网络中的每个边进行加权。 然后,通过快速的启发式过程创建一个初始分区,包括一些由那些潜在的“领导者节点”主导的集群。 第三,潜在的基于游戏的加权模块化优化用于改善初始分区。 最后,我们介绍了潜在吸引聚类的概念,然后使用简单的双阈值过程发现图的重叠分区。