An official website of the United States government
Networks that provide agents with access to a common database of the agents' actions enable an agent to easily learn by observing the actions of others, but are also susceptible to manipulation by “fake” agents. Prior work has studied a model for the impact of such fake agents on ordinary (rational) agents in a sequential Bayesian observational learning framework. That model assumes that ordinary agents do not have an ex-ante bias in their actions and that they follow their private information in case of an ex-post tie between actions. This paper builds on that work to study the effect of fake agents on the welfare obtained by ordinary agents under different ex-ante biases and different tie-breaking rules. We show that varying either of these can lead to cases where, unlike in the prior work, the addition of fake agents leads to a gain in welfare. This implies that in such cases, if fake agents are absent or are not adequately present, an altruistic platform could artificially introduce fake actions to effect improved learning.
more »
« less
Detecting Aberrant Linking Behavior in Directed Networks [Detecting Aberrant Linking Behavior in Directed Networks]
Agents with aberrant behavior are commonplace in today’s networks. There are fake profiles in social media, malicious websites on the internet, and fake news sources that are prolific in spreading misinformation. The distinguishing characteristic of networks with aberrant agents is that normal agents rarely link to aberrant ones. Based on this manifested behavior, we propose a directed Markov Random Field (MRF) formulation for detecting aberrant agents. The formulation balances two objectives: to have as few links as possible from normal to aberrant agents, as well as to deviate minimally from prior information (if given). The MRF formulation is solved optimally and efficiently. We compare the optimal solution for the MRF formulation to existing algorithms, including PageRank, TrustRank, and AntiTrustRank. To assess the performance of these algorithms, we present a variant of the modularity clustering metric that overcomes the known shortcomings of modularity in directed graphs. We show that this new metric has desirable properties and prove that optimizing it is NP-hard. In an empirical experiment with twenty-three different datasets, we demonstrate that the MRF method outperforms the other detection algorithms.
more »
« less
- Award ID(s):
- 1760102
- PAR ID:
- 10357234
- Date Published:
- Journal Name:
- Proceedings of the 11th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management
- Volume:
- IC3K 2019
- Page Range / eLocation ID:
- 72 to 82
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Epidemic containment has long been a crucial task in many high-stake application domains, ranging from public health to misinformation dissemination. Existing studies for epidemic containment are primarily focused on undirected networks, assuming that the infection rate is constant throughout the contact network regardless of the strength and direction of contact. However, such an assumption can be unrealistic given the asymmetric nature of the real-world infection process. To tackle the epidemic containment problem in directed networks, simply grafting the methods designed for undirected network can be problematic, as most of the existing methods rely on the orthogonality and Lipschitz continuity in the eigensystem of the underlying contact network, which do not hold for directed networks. In this work, we derive a theoretical analysis on the general epidemic threshold condition for directed networks and show that such threshold condition can be used as an optimization objective to control the spread of the disease. Based on the epidemic threshold, we propose an asymptotically greedy algorithm DINO (DIrected NetwOrk epidemic containment) to identify the most critical nodes for epidemic containment. The proposed algorithm is evaluated on real-world directed networks, and the results validate its effectiveness and efficiency.more » « less
-
Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P.S.; Vaughan, J. Wortman (Ed.)The prevalence of graph-based data has spurred the rapid development of graph neural networks (GNNs) and related machine learning algorithms. Yet, despite the many datasets naturally modeled as directed graphs, including citation, website, and traffic networks, the vast majority of this research focuses on undirected graphs. In this paper, we propose MagNet, a GNN for directed graphs based on a complex Hermitian matrix known as the magnetic Laplacian. This matrix encodes undirected geometric structure in the magnitude of its entries and directional information in their phase. A charge parameter attunes spectral information to variation among directed cycles. We apply our network to a variety of directed graph node classification and link prediction tasks showing that MagNet performs well on all tasks and that its performance exceeds all other methods on a majority of such tasks. The underlying principles of MagNet are such that it can be adapted to other GNN architectures.more » « less
-
The study of linear-quadratic stochastic differential games on directed networks was initiated in Feng, Fouque & Ichiba [7]. In that work, the game on a directed chain with finite or infinite players was defined as well as the game on a deterministic directed tree, and their Nash equilibria were computed. The current work continues the analysis by first developing a random directed chain structure by assuming the interaction between every two neighbors is random. We solve explicitly for an open-loop Nash equilibrium for the system and we find that the dynamics under equilibrium is an infinite-dimensional Gaussian process described by a Catalan Markov chain introduced in [7]. The discussion about stochastic differential games is extended to a random two-sided directed chain and a random directed tree structure.more » « less
-
null (Ed.)The study of linear-quadratic stochastic differential games on directed networks was initiated in Feng, Fouque & Ichiba [7]. In that work, the game on a directed chain with finite or infinite players was defined as well as the game on a deterministic directed tree, and their Nash equilibria were computed. The current work continues the analysis by first developing a random directed chain structure by assuming the interaction between every two neighbors is random. We solve explicitly for an open-loop Nash equilibrium for the system and we find that the dynamics under equilibrium is an infinite-dimensional Gaussian process described by a Catalan Markov chain introduced in [7]. The discussion about stochastic differential games is extended to a random two-sided directed chain and a random directed tree structure.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.5220/0008069600720082
