On Optimization of Complete Social Networks

Weldegebriel A. T., Stodolsky B. Y.

LOBACHEVSKII JOURNAL OF MATHEMATICS, cilt.40, sa.1, ss.106-113, 2019 (ESCI) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 40 Sayı: 1
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1134/s199508021901013x
  • Dergi Adı: LOBACHEVSKII JOURNAL OF MATHEMATICS
  • Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI), Scopus
  • Sayfa Sayıları: ss.106-113
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

A balanced social network is a social network where, for any member of the social network, the following two statements are true; a friend of my friend is my friend and an enemy of my enemy is my friend. In this paper we demonstrate a polynomial time greedy algorithm that balances any complete social network with n members by changing at most [n(2)/4 - n/2] of the initial relationships between the members of the network. We also demonstrate that the problem of determining the minimum number of relationships that needs to change so that a complete social network, where each member has at least as many friends as enemies, becomes balanced is still NP-Complete.