• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Ji, Sai (Ji, Sai.) | Dong, Yinhong (Dong, Yinhong.) | Du, Donglei (Du, Donglei.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川)

Indexed by:

CPCI-S EI Scopus

Abstract:

Lower bounded correlation clustering problem is a generalization of the classical correlation clustering problem, which has many applications in protein interaction networks, cross-lingual link detection, and communication networks, etc. In the lower bounded correlation clustering problem, we are given a complete graph and an integer L. Each edge is labelled either by a positive sign + or a negative sign - whenever the two endpoints of the edge are similar or dissimilar respectively. The goal of this problem is to partition the vertex set into several clusters, subject to an lower bound L on the sizes of clusters so as to minimize the number of disagreements, which is the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. In this paper, we propose the lower bounded correlation clustering problem and formulate the problem as an integer program. Furthermore, we provide two polynomial time algorithms with constant approximate ratios for the lower bounded correlation clustering problem on some special graphs.

Keyword:

Polynomial time Correlation clustering Lower bounded Approximation algorithm

Author Community:

  • [ 1 ] [Ji, Sai]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 2 ] [Dong, Yinhong]SouthCentral Univ Nat, Sch Management, Wuhan 430074, Hubei, Peoples R China
  • [ 3 ] [Du, Donglei]Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada
  • [ 4 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

COMPUTATIONAL DATA AND SOCIAL NETWORKS, CSONET 2021

Year: 2021

Volume: 13116

Page: 39-49

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

Affiliated Colleges:

Online/Total:298/10797099
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.