The problem of finding dense components of a graph is a widely explored area in data analysis, with diverse applications in fields and branches of study including community mining, spam detection, computer security and bioinformatics. This research project explores previously available algorithms in order to study them and identify potential modifications that could result in an improved version with considerable performance and efficiency leap. Furthermore, efforts were also steered towards devising a novel algorithm for the problem of densest subgraph discovery. This paper presents an improved implementation of a widely used densest subgraph discovery algorithm and a novel parallel algorithm which produces better results than a 2-approximation.
翻译:在数据分析中,找到图表中密度高的成分是一个广泛探讨的领域,在研究领域和分支,包括社区采矿、垃圾邮件探测、计算机安全和生物信息学领域应用各异,该研究项目探索了以前现有的算法,以便研究这些算法,并查明可能作出哪些修改,从而产生改进的版本,具有相当大的性能和效率飞跃;此外,还努力为最密集的子层发现问题设计一种新的算法;本文件介绍了对广泛使用的密度最深的子层发现算法和新颖的平行算法的改进实施,其结果优于2接近的结果。