Computing an effective decision making group of a society using social network analysis

Donghyun Kim (), Deying Li (), Omid Asgari (), Yingshu Li (), Alade O. Tokuta () and Heekuck Oh ()
Additional contact information
Donghyun Kim: North Carolina Central University
Deying Li: Renmin University of China
Omid Asgari: North Carolina Central University
Yingshu Li: Georgia State University
Alade O. Tokuta: North Carolina Central University
Heekuck Oh: Hanyang University

Journal of Combinatorial Optimization, 2014, vol. 28, issue 3, No 6, 577-587

Abstract: Abstract Recent years have witnessed how much a decision making group can be dysfunctional due to the extreme hyperpartisanship. While partisanship is crucial for the representatives to pursue the wishes of those whom they represent for, such an extremism results in a severe gridlock in the decision making progress, and makes themselves highly inefficient. It is known that such a problem can be mitigated by having negotiators in the group. This paper investigates the potential of social network analysis techniques to choose an effective leadership group of a society such that it suffers less from the extreme hyperpartisanship. We establish three essential requirements for an effective representative group, namely Influenceability, Partisanship, and Bipartisanship. Then, we formulate the problem of finding a minimum size representative group satisfying the three requirements as the minimum connected $$k$$ k -core dominating set problem (MC $$k$$ k CDSP), and show its NP-hardness. We introduce an extension of MC $$k$$ k CDSP, namely MC $$k$$ k CDSP-C, which assumes the society has a number of sub-communities and requires at least one representative from each sub-community should be in the leadership. We also propose an approximation algorithm for a subclass of MC $$k$$ k CDSP with $$k=2$$ k = 2 , and show an $$\alpha $$ α -approximation algorithm of MC $$k$$ k CDSP can be used to obtain an $$\alpha $$ α -approximation algorithm of MC $$k$$ k CDSP-SC.

Keywords: Dominating set; Social networks; Approximation algorithm; $$k$$ k -core; Vertex connectivity (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9687-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:28:y:2014:i:3:d:10.1007_s10878-013-9687-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9687-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().