Community detection is a fundamental network-analysis primitive with a variety of applications in diverse domains. Although the modularity introduced by Newman and Girvan (2004) has widely been used as a quality function for community detection, it has some drawbacks. The modularity density introduced by Li et al. (2008) is known to be an effective alternative to the modularity, which mitigates one of the drawbacks called the resolution limit. A large body of work has been devoted to designing exact and heuristic methods for modularity density maximization, without any computational complexity analysis. In this study, we investigate modularity density maximization from both algorithmic and computational complexity aspects. Specifically, we first accelerate column generation for the modularity density maximization problem. To this end, we point out that the auxiliary problem appearing in column generation can be viewed as a dense subgraph discovery problem. Then we employ a well-known strategy for dense subgraph discovery, called the greedy peeling, for approximately solving the auxiliary problem. Moreover, we reformulate the auxiliary problem to a sequence of $0$--$1$ linear programming problems, enabling us to compute its optimal value more efficiently and to get more diverse columns. Computational experiments using a variety of real-world networks demonstrate the effectiveness of our proposed algorithm. Finally, we show the NP-hardness of a slight variant of the modularity density maximization problem, where the output partition has to have two or more clusters, as well as showing the NP-hardness of the auxiliary problem.


翻译:社区检测是一个基本的网络分析原始,在不同领域的应用多种多样。尽管Newman和Girvan(2004年)引入的模块化密度已被广泛用作社区检测的一种质量功能,但它有一些缺点。Li等人(2008年)引入的模块密度被认为是模块性的一种有效替代,它缓解了一个称为解析极限的缺陷。大量工作致力于设计模块性密度最大化的精确和超常方法,而没有任何计算复杂性分析。在这项研究中,我们从算法和计算复杂性两个方面对模块性密度最大化进行了调查。具体地说,我们首先加快模块性密度最大化问题的柱子生成。为此,我们指出,列生成中的辅助问题可被视为一个密集的子成份发现问题。然后,我们采用了一个众所周知的密集子谱发现策略,要求贪婪剥离,以大致解决辅助性问题。此外,我们将辅助问题改写成一个费用-1美元线性编程问题序列,使我们能够更高效地配置其优化的硬性值,并最后用更多样化的轨迹显示我们的拟议的细度矩阵的精度。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
专知会员服务
60+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
15+阅读 · 2020年2月6日
VIP会员
相关VIP内容
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
72+阅读 · 2022年6月28日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
专知会员服务
60+阅读 · 2020年3月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员