On Optimization of Complete Social Networks
- Авторлар: Weldegebriel A.1, Stodolsky B.1
-
Мекемелер:
- Istanbul Technical University, Fen-Edebiyat Faculty, Department of Mathematics B1-303
- Шығарылым: Том 40, № 1 (2019)
- Беттер: 106-113
- Бөлім: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/203849
- DOI: https://doi.org/10.1134/S199508021901013X
- ID: 203849
Дәйексөз келтіру
Аннотация
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 ⌈n2/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.
Негізгі сөздер
Авторлар туралы
A. Weldegebriel
Istanbul Technical University, Fen-Edebiyat Faculty, Department of Mathematics B1-303
Хат алмасуға жауапты Автор.
Email: weldegebriel@itu.edu.tr
Түркия, Maslak, Istanbul, 34469
B. Stodolsky
Istanbul Technical University, Fen-Edebiyat Faculty, Department of Mathematics B1-303
Хат алмасуға жауапты Автор.
Email: stodolsky@itu.edu.tr
Түркия, Maslak, Istanbul, 34469