On Optimization of Complete Social Networks

被引：0
|
作者：
Weldegebriel, A. T. [1 ]
Stodolsky, B. Y. [1 ]
机构：
[1] Istanbul Tech Univ, Fen Edebiyat Fac, Dept Math B1 303, TR-34469 Istanbul, Turkey
来源：
LOBACHEVSKII JOURNAL OF MATHEMATICS | 2019年 / 40卷 / 01期
关键词：
Balanced signed graphs; Graph algorithms;
D O I：
10.1134/S199508021901013X
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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.
引用
收藏
页码：106 / 113
页数：8
相关论文
共 50 条
  • [31] Optimization-Based Influencing of Village Social Networks in a Counterinsurgency
    Hung, Benjamin W. K.
    Kolitz, Stephan E.
    Ozdaglar, Asuman
    SOCIAL COMPUTING, BEHAVIORAL-CULTURAL MODELING AND PREDICTION, 2011, 6589 : 10 - +
  • [32] Cyclic Entropy Optimization of Social Networks using an Evolutionary Algorithm
    El-Sayed, Nosayba
    Mahdi, Khaled
    Safar, Maytham
    PROCEEDINGS OF THE 2009 INTERNATIONAL CONFERENCE OF COMPUTATIONAL SCIENCES AND ITS APPLICATIONS, 2009, : 9 - +
  • [33] Stochastic Dynamic Programming Model for Revenue Optimization in Social Networks
    Hosein, Patrick
    Lawrence, Trisha
    2015 IEEE 11TH INTERNATIONAL CONFERENCE ON WIRELESS AND MOBILE COMPUTING, NETWORKING AND COMMUNICATIONS (WIMOB), 2015, : 378 - 383
  • [34] Optimization of the Critical Diameter and Average Path Length of Social Networks
    Du, Haifeng
    He, Xiaochen
    Du, Wei
    Feldman, Marcus W.
    COMPLEXITY, 2017,
  • [35] Ant Colony Optimization for the Control of Pollutant Spreading on Social Networks
    Chen, Wei-Neng
    Tan, Da-Zhao
    Yang, Qiang
    Gu, Tianlong
    Zhang, Jun
    IEEE TRANSACTIONS ON CYBERNETICS, 2020, 50 (09) : 4053 - 4065
  • [36] Optimization-Based Influencing of Village Social Networks in a Counterinsurgency
    Hung, Benjamin W. K.
    Kolitz, Stephan E.
    Ozdaglar, Asuman
    ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY, 2013, 4 (03)
  • [37] Trust Calculation with Ant Colony Optimization in Online Social Networks
    Sanadhya, Shashvat
    Singh, Shailendra
    ELEVENTH INTERNATIONAL CONFERENCE ON COMMUNICATION NETWORKS, ICCN 2015/INDIA ELEVENTH INTERNATIONAL CONFERENCE ON DATA MINING AND WAREHOUSING, ICDMW 2015/NDIA ELEVENTH INTERNATIONAL CONFERENCE ON IMAGE AND SIGNAL PROCESSING, ICISP 2015, 2015, 54 : 186 - 195
  • [38] An Ant Colony Optimization Method to Detect Communities in Social Networks
    Javadi, Saeed H. S.
    Khadivi, Shahram
    Shiri, M. Ebrahim
    Xu, Jia
    2014 PROCEEDINGS OF THE IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM 2014), 2014, : 200 - 203
  • [39] An ant colony optimization approach to expert identification in social networks
    Ahmad, Muhammad Aurangzeb
    Srivastava, Jaideep
    SOCIAL COMPUTING, BEHAVIORAL MODELING AND PREDICTION, 2008, : 120 - 128
  • [40] Online Discrete Optimization in Social Networks in the Presence of Knightian Uncertainty
    Raginsky, Maxim
    Nedic, Angelia
    OPERATIONS RESEARCH, 2016, 64 (03) : 662 - 679
12345