Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Network partitioning algorithms as cooperative games.

ABSTRACT: The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting dense subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolutions. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity-based approach and its generalizations as well as ratio cut and normalized cut methods can be viewed as particular cases of the hedonic games. Finally, for approaches based on potential hedonic games we suggest a very efficient computational scheme using Gibbs sampling.

SUBMITTER: Avrachenkov KE

PROVIDER: S-EPMC6208787 | biostudies-other | 2018

REPOSITORIES: biostudies-other

ACCESS DATA

Json Xml

Publications

Network partitioning algorithms as cooperative games.

Avrachenkov Konstantin E KE Kondratev Aleksei Y AY Mazalov Vladimir V VV Rubanov Dmytro G DG

Computational social networks 20181028 1

The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting dense subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is ...[more]

PMID: 30416938

Similar Datasets

Algorithms, games, and evolution.

Project description:Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced the whole of Life as we see it around us. There is a computational way to articulate the same amazement: "What algorithm could possibly achieve all this in a mere three and a half billion years?" In this paper we propose an answer: We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known in computer science to be surprisingly powerful and versatile. MWUA maximizes a tradeoff between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution.

| S-EPMC4115542 | biostudies-literature

Neural mechanisms of belief inference during cooperative games.

Project description:Humans have the arguably unique ability to understand the mental representations of others. For success in both competitive and cooperative interactions, however, this ability must be extended to include representations of others' belief about our intentions, their model about our belief about their intentions, and so on. We developed a "stag hunt" game in which human subjects interacted with a computerized agent using different degrees of sophistication (recursive inferences) and applied an ecologically valid computational model of dynamic belief inference. We show that rostral medial prefrontal (paracingulate) cortex, a brain region consistently identified in psychological tasks requiring mentalizing, has a specific role in encoding the uncertainty of inference about the other's strategy. In contrast, dorsolateral prefrontal cortex encodes the depth of recursion of the strategy being used, an index of executive sophistication. These findings reveal putative computational representations within prefrontal cortex regions, supporting the maintenance of cooperation in complex social decision making.

| S-EPMC2967416 | biostudies-literature

Games and enculturation: A cross-cultural analysis of cooperative goal structures in Austronesian games.

Project description:While most animals play, only humans play games. As animal play serves to teach offspring important life-skills in a safe scenario, human games might, in similar ways, teach important culturally relevant skills. Humans in all cultures play games; however, it is not clear whether variation in the characteristics of games across cultural groups is related to group-level attributes. Here we investigate specifically whether the cooperativeness of games covaries with socio-ecological differences across cultural groups. We hypothesize that cultural groups that engage in frequent inter-group conflict, cooperative sustenance acquisition, or that have less stratified social structures, might more frequently play cooperative games as compared to groups that do not share these characteristics. To test these hypotheses, we gathered data from the ethnographic record on 25 ethnolinguistic groups in the Austronesian language family. We show that cultural groups with higher levels of inter-group conflict and cooperative land-based hunting play cooperative games more frequently than other groups. Additionally, cultural groups with higher levels of intra-group conflict play competitive games more frequently than other groups. These findings indicate that games are not randomly distributed among cultures, but rather relate to the socio-ecological settings of the cultural groups that practice them. We argue that games serve as training grounds for group-specific norms and values and thereby have an important function in enculturation during childhood. Moreover, games might server an important role in the maintenance of cultural diversity.

| S-EPMC8612520 | biostudies-literature

Confusion cannot explain cooperative behavior in public goods games.

Project description:Some scholars find that behavioral variation in the public goods game is explained by variations in participants' understanding of how to maximize payoff and that confusion leads to cooperation. Their findings lead them to question the common assumption in behavioral economics experiments that choices reflect motivations. We conduct two experiments, in which we minimize confusion by providing participants with increased training. We also introduce a question that specifically assesses participants' understanding of payoff maximization choices. Our experimental results show that the distribution of behavior types is significantly different when participants play with computers versus humans. A significant increase in contributions is also observed when participants play with humans compared to when they play with computers. Moreover, social norms may be the main motive for contributions when playing with computers. Our findings suggest that social preferences, rather than confusion, play a crucial role in determining contributions in public goods games when playing with humans. We therefore argue that the assumption in behavioral economics experiments that choices reveal motivations is indeed valid.

| S-EPMC10927562 | biostudies-literature

Partitioning clustering algorithms for protein sequence data sets.

Project description:BackgroundGenome-sequencing projects are currently producing an enormous amount of new sequences and cause the rapid increasing of protein sequence databases. The unsupervised classification of these data into functional groups or families, clustering, has become one of the principal research objectives in structural and functional genomics. Computer programs to automatically and accurately classify sequences into families become a necessity. A significant number of methods have addressed the clustering of protein sequences and most of them can be categorized in three major groups: hierarchical, graph-based and partitioning methods. Among the various sequence clustering methods in literature, hierarchical and graph-based approaches have been widely used. Although partitioning clustering techniques are extremely used in other fields, few applications have been found in the field of protein sequence clustering. It is not fully demonstrated if partitioning methods can be applied to protein sequence data and if these methods can be efficient compared to the published clustering methods.MethodsWe developed four partitioning clustering approaches using Smith-Waterman local-alignment algorithm to determine pair-wise similarities of sequences. Four different sets of protein sequences were used as evaluation data sets for the proposed methods.ResultsWe show that these methods outperform several other published clustering methods in terms of correctly predicting a classifier and especially in terms of the correctness of the provided prediction. The software is available to academic users from the authors upon request.

| S-EPMC2678123 | biostudies-literature

Social Stratification and Cooperative Behavior in Spatial Prisoners' Dilemma Games.

Project description:It has been a long-lasting pursuit to promote cooperation, and this study aims to promote cooperation via the combination of social stratification and the spatial prisoners' dilemma game. It is previously assumed that agents share the identical payoff matrix, but the stratification or diversity exists and exerts influences in real societies. Thus, two additional classes, elites and scoundrels, derive from and coexist with the existing class, commons. Three classes have different payoff matrices. We construct a model where agents play the prisoners' dilemma game with neighbors. It indicates that stratification and temptation jointly influence cooperation. Temptation permanently reduces cooperation; elites play a positive role in promoting cooperation while scoundrels undermine it. As the temptation getting larger and larger, elites play a more and more positive and critical role while scoundrels' negative effect becomes weaker and weaker, and it is more obvious when temptation goes beyond its threshold.

| S-EPMC4501745 | biostudies-literature

Detecting overlapping communities in complex networks using non-cooperative games.

Project description:Detecting communities in complex networks is of paramount importance, and its wide range of real-life applications in various areas has caused a lot of attention to be paid to it, and many efforts have been made to have efficient and accurate algorithms for this purpose. In this paper, we proposed a non-cooperative game theoretic-based algorithm that is able to detect overlapping communities. In this algorithm, nodes are regarded as players, and communities are assumed to be groups of players with similar strategies. Our two-phase algorithm detects communities and the overlapping nodes in separate phases that, while increasing the accuracy, especially in detecting overlapping nodes, brings about higher algorithm speed. Moreover, there is no need for setting parameters regarding the size or number of communities, and the absence of any stochastic process caused this algorithm to be stable. By appropriately adjusting stop criteria, our algorithm can be categorized among those with linear time complexity, making it highly scalable for large networks. Experiments on synthetic and real-world networks demonstrate our algorithm's good performance compared to similar algorithms in terms of detected overlapping nodes, detected communities size distribution, modularity, and normalized mutual information.

| S-EPMC9247049 | biostudies-literature

Analysis of concordance of different haplotype block partitioning algorithms.

Project description:BackgroundDifferent classes of haplotype block algorithms exist and the ideal dataset to assess their performance would be to comprehensively re-sequence a large genomic region in a large population. Such data sets are expensive to collect. Alternatively, we performed coalescent simulations to generate haplotypes with a high marker density and compared block partitioning results from diversity based, LD based, and information theoretic algorithms under different values of SNP density and allele frequency.ResultsWe simulated 1000 haplotypes using the standard coalescent for three world populations--European, African American, and East Asian--and applied three classes of block partitioning algorithms--diversity based, LD based, and information theoretic. We assessed algorithm differences in number, size, and coverage of blocks inferred under different conditions of SNP density, allele frequency, and sample size. Each algorithm inferred blocks differing in number, size, and coverage under different density and allele frequency conditions. Different partitions had few if any matching block boundaries. However they still overlapped and a high percentage of total chromosomal region was common to all methods. This percentage was generally higher with a higher density of SNPs and when rarer markers were included.ConclusionA gold standard definition of a haplotype block is difficult to achieve, but collecting haplotypes covered with a high density of SNPs, partitioning them with a variety of block algorithms, and identifying regions common to all methods may be the best way to identify genomic regions that harbor SNP variants that cause disease.

| S-EPMC1343594 | biostudies-literature

The behavioral effects of cooperative and competitive board games in preschoolers.

Project description:Traditional board games are a common social activity for many children, but little is known about the behavioral effects of this type of game. The current study aims to explore the behavioral effects of cooperative and competitive board games in four-to-six-year-old children (N = 65). Repeatedly during 6 weeks, children in groups of four played either cooperative or competitive board games in a between-subject design, and shortly after each game conducted a task in which children's cooperative, prosocial, competitive, and antisocial behavior were observed. The type of board game did not have an effect on cooperative, prosocial or antisocial behavior. Cooperative and competitive board games elicited equal amounts of cooperative and prosocial behavior, which suggest that board games, regardless of type, could have positive effects on preschoolers' social behavior. Our results suggest that children may compete more after playing competitive board games; but the measure of competitive behavior in particular was unreliable. Preschoolers enjoyed playing cooperative board games more than competitive board games, which may be one reason to prefer their use.

| S-EPMC8248432 | biostudies-literature

Interdependent network reciprocity in evolutionary games.

Project description:Besides the structure of interactions within networks, also the interactions between networks are of the outmost importance. We therefore study the outcome of the public goods game on two interdependent networks that are connected by means of a utility function, which determines how payoffs on both networks jointly influence the success of players in each individual network. We show that an unbiased coupling allows the spontaneous emergence of interdependent network reciprocity, which is capable to maintain healthy levels of public cooperation even in extremely adverse conditions. The mechanism, however, requires simultaneous formation of correlated cooperator clusters on both networks. If this does not emerge or if the coordination process is disturbed, network reciprocity fails, resulting in the total collapse of cooperation. Network interdependence can thus be exploited effectively to promote cooperation past the limits imposed by isolated networks, but only if the coordination between the interdependent networks is not disturbed.

| S-EPMC3560361 | biostudies-other

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data