New Zealand

Touhid Bhuiyan, Audun Josang and Yue Xu (March 1st 2010). Trust and Reputation Management in Web-based Social Network, Web Intelligence and Intelligent Agents, Zeeshan-Ul-Hassan Usmani, IntechOpen, DOI: 10.5772/8375. 

Mingyu Zhou, Lihua Li, Yi Wang and Ping Zhang (November 1st 2008). Greedy Algorithm: Exploring Potential of Link Adaptation Technique in Wideband Wireless Communication Systems, Greedy Algorithms, Witold Bednorz, IntechOpen, DOI: 10.5772/6356.

We consider the influence maximization problem (selecting k seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a (1−(1−1/k)^k+Ω(1/k^3))-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic (1−(1−1/k)^k) bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a (1−(1−1/k)^k+O(1/k^0.2)) approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a (1−(1−1/k)^k)-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a (1−(1−1/k)^k+c) approximation for constant c&gt;0. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio (1−(1−1/k)^k) is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a (1−(1−1/k)^k+f(k))-approximation for any positive function f(k). The result in setting 2) is again in a sharp contrast to Khanna and Lucier&#39;s (1−(1−1/k)^k+c)-approximation result for the independent cascade model, where the (1−(1−1/k)^k+c) approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.


AAMAS 2020

Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

linear threshold model

greedy algorithm

social network

influence maximization

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

We consider the influence maximization problem (selecting k seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a (1−(1−1/k)^k+Ω(1/k^3))-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic (1−(1−1/k)^k) bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a (1−(1−1/k)^k+O(1/k^0.2)) approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a (1−(1−1/k)^k)-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a (1−(1−1/k)^k+c) approximation for constant c>0. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio (1−(1−1/k)^k) is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a (1−(1−1/k)^k+f(k))-approximation for any positive function f(k). The result in setting 2) is again in a sharp contrast to Khanna and Lucier's (1−(1−1/k)^k+c)-approximation result for the independent cascade model, where the (1−(1−1/k)^k+c) approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.


technical paper

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

MB-DPOP is an important complete algorithm for solving Distributed Constraint Optimization Problems (DCOPs) by exploiting a cycle-cut idea to implement memory-bounded inference. However, each cluster root in the algorithm is responsible for enumerating all the instantiations of its cycle-cut nodes, which would cause redundant inferences when its branches do not have the same cycle-cut nodes. Additionally, a large number of cycle-cut nodes and the iterative nature of MB-DPOP further exacerbate the pathology. As a result, MB-DPOP could suffer from huge coordination overheads and cannot scale up well. Therefore, we present RMB-DPOP which incorporates several novel mechanisms to reduce redundant inferences and improve the scalability of MB-DPOP. First, using the independence among the cycle-cut nodes in different branches, we distribute the enumeration of instantiations into different branches whereby the number of nonconcurrent instantiations reduces significantly and each branch can perform memory bounded inference asynchronously. Then, taking the topology into the consideration, we propose an iterative allocation mechanism to choose the cycle-cut nodes that cover a maximum of active nodes in a cluster and break ties according to their relative positions in a pseudo-tree. Finally, a caching mechanism is proposed to further reduce unnecessary inferences when the historical results are compatible with the current instantiations. We theoretically show that with the same number of cycle-cut nodes RMB-DPOP requires as many messages as MB-DPOP in the worst case and the experimental results show our superiorities over the state-of-the-art.


RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences

A Novel Individually Rational Objective In Multi*Agent Multy-Armed Bandits: Algorithms and Regret Bounds

Goal reasoning has been attracting much attention in AI recently. Here, we consider how an agent changes its goals as a result of interaction with humans and peers. In particular, we draw upon a model developed in Behavioral Science, the Elementary Pragmatic Model (EPM). We show how the EPM principles can be incorporated into a sophisticated theory of goal change based on the Situation Calculus. The resulting logical theory supports agents with a wide variety of relational styles, including some that we may consider irrational or creative. This lays the foundations for building autonomous agents that interact with humans in a rich and realistic way, as required by advanced Human-AI collaboration applications


Goal Formation through Interaction in the Situation Calculus: A Formal Account Grounded in Behavioral Science

The Chamberlin-Courant (CC) family of committee selection rules aim to select a committee of size $k$ from a set of $m$ candidates to maximize the satisfaction of $n$ agents. The satisfaction of an agent from a committee depends only on the rank of her favorite candidate and is determined by a satisfaction function. Unfortunately, computing an optimal committee of size $k$ is hard in general, which has led to the development of approximation algorithms that select a committee of size $k$, which guarantees some fraction of the optimal satisfaction. However, there is often some flexibility in the size of the committee to be selected.

In this paper, we initiate the study of size-relaxed committee selection for the family of CC rules. Our main results are polynomial-time algorithms to select committees of size at most $k\cdot O(\log n)$, whose satisfaction is guaranteed to be at least that of the optimal committee of size $k$, and show that this is tight. We also provide a constant-factor approximation algorithm for a class of approval ballot based CC rules.


Size-Relaxed Committee Selection under the Chamberlin-Courant Rule

We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures that capture the extent to which neighbors of a certain node can help it complete relevant tasks.


It's Not Whom You Know, It's What You (or your friends) Can Do: Coalitional Frameworks for Network Centralities

This talk is about how to design differentially private algorithm in contextual dynamic pricing setting. 


Differentially Private Contextual Dynamic Pricing

In many practical scenarios, a population is divided into disjoint groups for better administration, such as electorates into political districts and students into school districts. However, grouping people arbitrarily may lead to biased partitions, raising concerns of gerrymandering in political districting and racial segregation in schools. To counter such issues, in this paper, we conceptualize such problems in a voting scenario, and given an initial grouping, we propose the Fair Regrouping problem to redistribute a given set of people into k groups, where each person has a preferred alternative and a set of groups they can be moved to, such that the maximum margin of victory of any group is minimized. We also propose the Fair Connected Regrouping problem which additionally requires the people within each group to be connected. We show that the Fair Regrouping problem is NP-complete for plurality voting even if we have only 3 alternatives, but admits polynomial time algorithms if everyone can be moved to any group. We further show that the Fair Connected Regrouping problem is NP-complete for plurality voting even if we have only 2 alternatives and k = 2. Finally, we propose heuristic algorithms for both problems and show their effectiveness in political districting in the U.K. and in lowering racial segregation in public schools in the U.S.


Minimizing Margin of Victory for  Fair Political and Educational Districting

Controlling recurrent infectious diseases is a vital yet complicated problem. A large portion of the controlling epidemic relies on patients visit clinics voluntarily. However, they may already transmit the disease to their contacts by the time they feel sick enough to visit the clinic, especially for conditions with a long incubation period. Therefore, active screening/case finding was deployed to provide a powerful yet expensive means to control disease spread in recent years. To make active screening success a given limit budget, one of the challenges that need to be addressed is that we do not know the exact state of each patient. Given the number of horizon and budget we have in each time step, we also need to plan our screening efficiently and screening the vital patients in time. Thus, we apply a reinforcement learning approach to solve active screening problems on the network SIS disease model. The first contribution of this work is that we identify three significant challenges in active screening problems: partially observable states, combinatorial action choice, high-dimensional state-action space. We further propose the corresponding solutions to overcome these challenges. Specifically, we resolve the issue of high-dimensional state-action space by encoding the actions and partially observable states into a lower dimension form, which is done by either manually, using domain expertise, or automatically, using the state of the art GCN approach. We show that our approach can scale up to large graphs and perform decently compared to other baselines of previous literature and current practice.

Who and When to Screen: Multi-Round Active Screening for Recurrent Infectious Diseases Under Uncertainty

How should one combine noisy information from diverse sources to make an inference about an objective ground truth? This frequently recurring, normative question lies at the core of statistics, machine learning, policy-making, and everyday life. It has been called "combining forecasts", "meta-analysis", "ensembling", and the "MLE approach to voting", among other names. Past studies typically assume that noisy votes are identically and independently distributed (i.i.d.), but this assumption is often unrealistic. Instead, we assume that votes are independent but not necessarily identically distributed and that our ensembling algorithm has access to certain auxiliary information related to the underlying model governing the noise in each vote. In our present work, we: (1) define our problem and argue that it reflects common and socially relevant real world scenarios, (2) propose a multi-arm bandit noise model and count-based auxiliary information set, (3) derive maximum likelihood aggregation rules for ranked and cardinal votes under our noise model, (4) propose, alternatively, to learn an aggregation rule using an order-invariant neural network, and (5) empirically compare our rules to common voting rules and naive experience-weighted modifications. We find that our rules successfully use auxiliary information to outperform the naive baselines.


Objective Social Choice

A serious challenge when finding influential actors in real-world social networks, to enable efficient community-wide interventions, is the lack of knowledge about the structure of the underlying network. Current state-of-the-art methods rely on hand-crafted sampling algorithms; these methods sample nodes and their neighbours in a carefully constructed order and choose opinion leaders from this discovered network to maximize influence spread in the(unknown) complete network.
In this work, we propose a reinforcement learning framework to discover effective network sampling heuristics by leveraging automatically learnt node and graph representations that encode important structural properties of the network. At training time, the method identifies portions of the network such that the nodes selected from this sampled subgraph can effectively influence nodes in the complete network. The output of this training is a transferable, adaptive policy that identifies an effective sequence of nodes to query on unseen graphs. The success of this policy is underpinned by a set of careful choices for embedding local and global information about the graph and providing appropriate reward signals during training. We experiment with real-world social networks from four different domains and show that the policies learned by our RL agent provide a 7-23% improvement over the current state-of-the-art method


Downloads

Next from AAMAS 2020

RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences

Similar lecture

Parameterized Approximation Algorithms for k-Center Clustering and Variants

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inferences

Similar lecture

Parameterized Approximation Algorithms for k-Center Clustering and Variants

Downloads