Community detection algorithm for boundary region processing based on submodular optimization
DOI:
CSTR:
Author:
Affiliation:

Clc Number:

TP181;TN99

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Overlapping regions often occur when non-overlapping community structure is obtained by clustering granulation method. The nodes in the non-overlapping parts of the community of the left side between two communities with overlapping parts were defined as positive regions. Then, the nodes on its right are denoted as the negative region, and nodes in the overlapping parts are denoted as the boundary region. In order to achieve better community structure, it is necessary to divide the nodes in the boundary region into nonoverlapping parts. Submodular optimization is widely used in machine learning, If the objective function has sub-modularity, it exists a simple greedy algorithm which can approximate the optimal solution of the problem with constant factor in polynomial time. In this paper, submodular optimization is introduced into the processing of nodes in overlapping communities. and a community detection algorithm (SO-CDA) for boundary region processing based on submodular optimization is proposed. The device location function is defined for submodular optimization, the partition of overlapping nodes is converted to the maximization of submodular function. The experimental results on seven real networks show that SO-CDA can effectively divide communities and achieve more stable performance.

    Reference
    Related
    Cited by
Get Citation
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:
  • Revised:
  • Adopted:
  • Online: June 15,2023
  • Published:
Article QR Code