基于遗传算法的大规模网络中最大集团的识别-研究论文

简介：
本论文提出一种利用遗传算法在大规模网络中高效识别最大集团的方法，为社交网络分析和社群检测提供了新的视角。 在图论领域里，“集团”指的是一个子图（完全连接），其中每个节点都与其他所有节点相连。最大集团问题的应用包括复杂网络中的功能单元识别、社交网络演化的建模以及社区检测等。解决这个问题的一个挑战是，它包含了一个NP-Hard问题——即对于大规模复杂的网络来说，在有限时间内枚举所有的集团是一个难题。 然而，通过应用启发式的优化算法，可以在合理的时间内找到这些复杂网路的最大集团。尽管最大团组问题是NP难的（例如旅行商问题、图着色问题和3-SAT等），但它们可以被简化为求解最大团的问题以实现多项式时间内的处理。值得注意的是，在所有可能的集团中，不属于任何其他更大集团子集的那个称为“最大派系”。在这些最大的群体里边，具有最多节点或最高权重的一个即被认为是网络中的最大集团。 研究者们提出了多种方法来识别网络中的团体。然而大多数的方法在分析大规模网路时都面临着计算成本过高的问题。本段落则提出了一种有效的遗传算法以枚举大规模网络中所有的群组，并通过与其他现有算法的复杂度比较，验证了这一新方法的有效性。