An approach for community detection in social networks based on cooperative games theory

Detecting communities is of great importance in social network analysis. However it is an issue that has not yet been satisfactorily solved, despite the efforts made by interdisciplinary research communities over the past few years, because of the nature of complexity in deciding how community structures should be recognized. In this paper we propose an approach based on cooperative game theory for community detection in social networks. We regard individuals as players, and regard communities as coalitions formed by players, and model community detection problem as the formation and optimization of coalitions. Furthermore, we define coalition profile for players to indicate coalitions that players joined, the order of a coalition profile is defined as the number of coalitions in a coalition profile, and we introduce a utility function to measure preference of coalition profiles. Accordingly, we propose an algorithm to detect a coalition profile with maximal utility function values. We have implemented the algorithms developed in this study and experimental results demonstrate the effectiveness of our approaches.     

Formal analysis of DeGroot Influence Problems using probabilistic model checking

DeGroot learning is a model of opinion diffusion and formation in a social network. We examine the behaviour of the DeGroot learning model when external strategic players that aim to influence the opinion formation process are introduced. More specifically, we consider the case of a single decision maker and that of two competing players, with a fixed number of possible influence actions for each of them. In the former case, the DeGroot model takes the form of a Markov Decision Process (MDP), while in the latter case it takes the form of a Stochastic Game (SG). These models are solved using probabilistic model checking techniques, as well as other solution techniques beyond model checking. The viability of our analysis is attested on a well-known social network, the Zachary’s karate club. Finally, the evaluation of influence in a social network simultaneously with the decision maker’s cost is supported, which is encoded as a multi-objective model checking problem.     

A note on competitive diffusion through social networks

We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then an equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then an equilibrium is not guaranteed to exist.     

Perfectly fair channel assignment in non-cooperative multi-radio multi-channel wireless networks

The channel assignment problem is very important in wireless networks. In this letter, we study the non-cooperative channel assignment problem in competitive multi-radio multi-channel wireless networks, with a focus on fairness issues. We propose a Nash equilibrium solution with stronger guarantee on fairness among players than existing works, by requiring a payment from each player. We show that, in our scheme, when system converges to a stable status achieving Nash equilibrium, all players obtain the same throughput. Simulation results verify that our scheme achieves perfect fairness.     

Adversarial classification using signaling games with an application to phishing detection

In adversarial classification, the interaction between classifiers and adversaries can be modeled as a game between two players. It is natural to model this interaction as a dynamic game of incomplete information, since the classifier does not know the exact intentions of the different types of adversaries (senders). For these games, equilibrium strategies can be approximated and used as input for classification models. In this paper we show how to model such interactions between players, as well as give directions on how to approximate their mixed strategies. We propose perceptron-like machine learning approximations as well as novel Adversary-Aware Online Support Vector Machines. Results in a real-world adversarial environment show that our approach is competitive with benchmark online learning algorithms, and provides important insights into the complex relations among players.     

Acquaintance-based trust model for the evolution of cooperation in business games

Reputation systems have been popular in several online market places involving anonymous players as it can provide crucial information on the trustworthiness of an object or individual player to combat selfish and deceptive behaviors from peers. Individual feedbacks on the quality of past association are the fundamental building blocks of reputation systems. Careful consideration in aggregating feedbacks from different sources is in fact very important in computing a reliable value for trust worthiness to facilitate decision making in a social dilemma situation like that of online market places. In this paper, we are considering a possible improvement to a reputation model like that of eBay, with our interest lying on investigating how the cooperativeness and population of cooperators would evolve if the weight of the feedback source was assigned on the basis of past association between players. We categorize the feedback sources into different types to define an aggregation method for trustworthiness assessment that considers applying a dynamically computed weight to each source of feedback. Our results show that breaking feedback sources on the basis of acquaintance and assigning weight accordingly favor the evolution of cooperativeness in the player society when compared to models which do not classify the feedback sources.     

Matrix games with missing,interval, and ambiguous lottery payoffs of pure strategy profiles and compound strategy profiles

In a matrix game, the interactions among players are based on the assumption that each player has accurate information about the payoffs of their interactions and the other players are rationally self‐interested. As a result, the players should definitely take Nash equilibrium strategies. However, in real‐life, when choosing their optimal strategies, sometimes the players have to face missing, imprecise (i.e., interval), ambiguous lottery payoffs of pure strategy profiles and even compound strategy profile, which means that it is hard to determine a Nash equilibrium. To address this issue, in this paper we introduce a new solution concept, called ambiguous Nash equilibrium, which extends the concept of Nash equilibrium to the one that can handle these types of ambiguous payoff. Moreover, we will reveal some properties of matrix games of this kind. In particular, we show that a Nash equilibrium is a special case of ambiguous Nash equilibrium if the players have accurate information of each player's payoff sets. Finally, we give an example to illustrate how our approach deals with real‐life game theory problems.     

Virtual worlds in competitive contexts: Analyzing eSports consumer needs

More recently, 3D graphical environments on the Internet, that is virtual worlds, have moved to the center of scientific interest. Since virtual worlds are suggested to mold social computing, research has predominately focused on collaborative virtual worlds. Yet, virtual worlds increasingly move to competitive environments leaving operating businesses with the question as to what to offer in order to fulfill customers’ needs. To close this knowledge gap, we examine competitive virtual worlds in terms of eSports services intrinsically tying cooperation and competition; we illuminate competitive and hedonic need gratifications of continuous eSports use. We apply Uses and Gratifications theory reporting on ten in-depth expert interviews as well as survey data collected from 360 eSports players. We reveal that both competitive (competition and challenge) and hedonic need gratifications (escapism) drive continuous eSports use.     

On the Allocation of Multiple Divisible Assets to Players with Different Utilities

When there is a dispute between players on how to divide multiple divisible assets, how should it be resolved? In this paper we introduce a multi-asset game model that enables cooperation between multiple agents who bargain on sharing K assets, when each player has a different value for each asset. It thus extends the sequential discrete Raiffa solution and the Talmud rule solution to multi-asset cases.     

Towards understanding how to design for social play in exertion games

Players invest significant physical effort when playing exertion games. In addition to improving physical health, exertion games are also believed to facilitate social play amongst players. Despite these advantages, our understanding of how to design these games to successfully support social play is limited. In this paper, we present a qualitative analysis of player data from “Table Tennis for Three”, a mediated exertion game for three players, that contributes to our understanding of how the design of an exertion game facilitates social play. We use the concept of “space” to frame our findings in order to create themes that can be used to analyze existing and to design future exertion games. We hope our work can support researchers gain an understanding of this exciting new field, while also help designers utilize the many benefits of exertion games.     

Design and validation of a knowledge map system—the case of construction industry in Taiwan

Knowledge map systems (KMSs) have recently received widespread attention. A review of the literature shows that relatively few studies explicitly address the issues of implementation and user evaluation of the system and are limited in application. In view of this dilemma, this study aims to integrate the key features of knowledge assets maps, knowledge sources maps, knowledge structure maps, and knowledge task maps in order to develop an operational KMS. Also, the technology acceptance model was used as the theoretical basis for the assessment of user acceptance of the system, which is validated using structural equation modeling. In terms of user acceptance assessment, our empirical results shows that the perceived usefulness and perceived ease of use will positively affect user attitude toward the proposed KMS. Also, our results suggest that social defense negatively moderates the effect of attitude toward the system on behavior intention. Furthermore, we found that the management system also positively moderates the effect of attitude toward the system on behavior intention. On the basis of theoretical evaluation and empirical investigation, we hope that the proposed construction of a knowledge system can serve as references for both academic and related practical fields.     

Optimal location policy for three competitive facilities

Competitive facility location problems have been investigated in many papers. In most, authors have applied location models with two competitors. In this paper three companies, which are mutually competitive, intend to locate their facilities in a linear market. It is well-known that Nash equilibrium solution for location problem does not include three competitive facilities. In this paper we present the optimal location strategies for three facilities. In our model we assume that the demands are continuously distributed in a linear market and the facilities are locating according to a specific order of sequence, A, B and C. We apply the Stackelberg equilibrium solutions for competitive location problems with three facilities. In our model, we consider the decision problems in three stages. In the first stage, we decide the optimal location of facility A, which is located optimally in respect to the remaining two facilities B and C. In the second stage, we determine the optimal location of facility B which is optimally located in respect to facility C, by utilizing the information on the location of facility A. Finally in the third stage problem we decide the location of facility C, optimally located by utilizing the information on the location of A and B. In the first stage, we need the optimal solutions of the second and third stages. In the second stage we need the optimal solution of the third stage problem. Therefore, first we solve the third stage problem which is the simplest. After that, we solve the second stage problem utilizing the optimal solution strategy of the third stage problem. In this paper we present the optimal location strategies for three facilities.     

INFLUENCE OF ENVIRONMENTAL CHANGES ON COOPERATIVE BEHAVIOR IN THE PRISONER'S DILEMMA GAME ON AN ARTIFICIAL SOCIAL MODEL

In this paper, by simulations on an artificial social model, we analyze cooperative behavior of agents playing the prisoner's dilemma game, in which each of the agents has the two strategies: cooperate and defect. Because defect yields a better payoff whichever strategy an opponent chooses, it is rational for an agent to choose defect in a single game or a finite number of games. However, it is known that a pair of cooperates can also be a Nash equilibrium pair if the players do not know when the game is over or the game is infinitely repeated. To investigate such cooperative behavior, we employ an artificial social model called the Sugarscape and carry out simulations on the model. Arranging three kinds of environments in the Sugarscape, we examine cooperative behavior of agents who are essentially selfish, in a sense that they maximize their payoffs, and investigate influence of environmental changes on the cooperative behavior.     

Knowledge sharing in dynamic virtual enterprises: A socio-technological perspective

The success of a virtual enterprise depends largely on the effective collaboration of its members in orchestrating their knowledge, skills, core competences and resources, in order to enhance competitive capabilities and respond better to business opportunities. In this paper we address the challenges of knowledge sharing in dynamic virtual enterprises. We take a socio-technological approach by proposing a human-centered knowledge sharing solution and architecture. Specifically, we propose a knowledge resource space model to represent heterogeneous knowledge resources, both explicit and implicit. We then introduce a knowledge sharing community model and adopt an agent based solution to perform the functions of knowledge sharing among members of a dynamic virtual enterprise. Our solution incorporates the concepts of agent society and semantic ontology. Knowledge sharing in dynamic virtual enterprises is performed with three types of ties: knowledge agent to knowledge agent, knowledge agent to knowledge item, and knowledge item to knowledge item. We measure agent-to-agent ties by preference correlation using the contribution degree of one agent to another and the preference similarity degree between two agents. We define a semantic view to show agent-to-item ties and use semantic links in the knowledge resource space model to reflect item-to-item ties. We also elaborate the co-evolution mechanism of collective intelligence across enterprises throughout the lifecycle of a dynamic virtual enterprise. A case study is presented to validate our approach.     

Supporting Dispute Handling in E-Commerce Transactions, a Framework and Related Methodologies

An E-commerce transaction is a means to conduct particular commercial activities using the global digital E-commerce infrastructure. We concentrate here on business to customer (B-to-C) E-commerce transactions. These transactions are based on protocols offered by the global infrastructure, primarily the Internet. Using electronic means to do business can greatly improve the efficiency of the business transactions. It, however, poses some problems that were rarely considered to be important before. One class of problems is caused by the behavior of untrusted participants. For reasons such as dishonesty, disputes may arise. In the general case, when a dispute arises an untrustworthy participant may have an arbitrary behavior, and may or may not cooperate with the dispute handling process. In this paper, we study one class of disputes where the participants have some limited willingness to cooperate, and the causes or demands by the initiators are directly related to the actions in the transactions in which the disputes arise. To this end, we first establish a correctness criterion by extending the existing notion of transactional atomicity to a broader context where the behavior of untrustworthy players is taken into consideration. We then introduce the concept of a dispute, and the difficulties to handle it caused by abnormal behavior of players. We introduce a strategy, benefit set, based on which a solution is built to circumvent that behavior. Due to the special features of E-commerce transactions, we propose a two-tier arbiter structure as the main mechanism in our solution.     

Ambiguous Bayesian Games

Bayesian games can handle the incomplete information about players' types. However, in real life, the information could be not only incomplete but also ambiguous for lack of sufficient evidence, i.e., a player cannot have a precise probability about each type of the other players. To address this issue, this paper firstly extends the Bayesian games to ambiguous Bayesian games. Then, we introduce the concept of a solution to this kind of games and discuss their properties, especially about solution existence, how the ambiguity degree and players' ambiguity attitude influence the outcomes of an ambiguous Bayesian game, the case of lower boundary probability, and the missing situation. We also illustrate our game model, especially in the public security domain.     

From PhotoWork to PhotoUse: exploring personal digital photo activities

People accumulate large collections of digital photos, which they use for individual, social, and utilitarian purposes. In order to provide suitable technologies for enjoying our expanding photo collections, it is essential to understand how and to what purpose these collections are used. Contextual interviews with 12 participants in their homes explored the use of digital photos, incorporating new photo activities that are offered by new technologies. Based on the qualitative analysis of the collected data, we give an overview of current photo activities, which we term PhotoUse. We introduce a model of PhotoUse, which emphasises the purpose of photo activities rather than the tools to support them. We argue for the use of our model to design tools to support the user’s individual and social goals pertaining to PhotoUse.     

Risk consideration and cooperation in the iterated prisoner’s dilemma

This paper investigates the cooperative behavior in the two-player iterated prisoner’s dilemma (IPD) game with the consideration of income stream risk. The standard deviation of one-move payoffs for players is defined for measuring the income stream risk, and thus the risk effect on the cooperation in the two-player IPD game is examined. A two-population coevolutionary learning model, embedded with a niching technique, is developed to search optimal strategies for two players to play the IPD game. As experimental results illustrate, risk-averse players perform better than risk-seeking players in cooperating with opponents. In particular, in the case with short game encounters, in which cooperation has been demonstrated to be difficult to achieve in previous work, a high level of cooperation can be obtained in the IPD if both players are risk-averse. The reason is that risk consideration induces players to negotiate for stable gains, which lead to steady mutual cooperation in the IPD. This cooperative pattern is found to be quite robust against low levels of noise. However, with increasingly higher levels of noise, only intermediate levels of cooperation can be achieved in games between two risk-averse players. Games with risk-seeking players get to even lower cooperation levels. By comparing the players’ strategies coevolved with and without a high level of noise, the main reason for the reduction in the extent of cooperation can be explained as the lack of contrition and forgiveness of players in the high-noise interactions. Moreover, although increasing encounter length is helpful in improving cooperation in the noiseless and low-noise IPD, we find that it may enforce the absence of contrition and forgiveness, and thus make cooperation even more difficult in the high-noise games.     

Cooperative global output regulation of heterogeneous second-order nonlinear uncertain multi-agent systems

In this paper, we study the cooperative global output regulation problem for a class of heterogeneous second order nonlinear uncertain multi-agent systems. We first introduce a type of distributed internal model that converts the cooperative global output regulation problem into the global robust stabilization problem of the so-called augmented multi-agent system. Then we further globally stabilize this augmented multi-agent system via a distributed state feedback control law, thus leading to the solution of the original problem. A special case of our result leads to the solution of the global leader-following consensus problem for the second order nonlinear multi-agent systems without satisfying the global Lipschitz condition.     

User opinion classification in social media: A global consistency maximization approach

Social media is a major platform for opinion sharing. In order to better understand and exploit opinions on social media, we aim to classify users with opposite opinions on a topic for decision support. Rather than mining text content, we introduce a link-based classification model, named global consistency maximization (GCM) that partitions a social network into two classes of users with opposite opinions. Experiments on a Twitter data set show that: (1) our global approach achieves higher accuracy than two baseline approaches and (2) link-based classifiers are more robust to small training samples if selected properly.