In this paper we investigate phenomena of spontaneous emergence or purposeful formation of highly organized structures in networks of related agents. We show that the formation of large organized structures requires exponentially large, in the size of the structures, networks. Our approach is based on Kolmogorov, or descriptional, complexity of networks viewed as finite size strings. We apply this approach to the study of the emergence or formation of simple organized, hierarchical, structures based on Sierpinski Graphs and we prove a Ramsey type theorem that bounds the number of vertices in Kolmogorov random graphs that contain Sierpinski Graphs as subgraphs. Moreover, we show that Sierpinski Graphs encompass close-knit relationships among their vertices that facilitate fast spread and learning of information when agents in their vertices are engaged in pairwise interactions modelled as two person games. Finally, we generalize our findings for any organized structure with succinct representations. Our work can be deployed, in particular, to study problems related to the security of networks by identifying conditions which enable or forbid the formation of sufficiently large insider subnetworks with malicious common goal to overtake the network or cause disruption of its operation.
相關內容
Medical ultrasound imaging is the most widespread real-time non-invasive imaging system and its formulation comprises signal transmission, signal reception, and image formation. Ultrasound signal transmission modelling has been formalized over the years through different approaches by exploiting the physics of the associated wave problem. This work proposes a novel computational framework for modelling the ultrasound signal transmission step in the time-frequency domain for a linear-array probe. More specifically, from the impulse response theory defined in the time domain, we derived a parametric model in the corresponding frequency domain, with appropriate approximations for the narrowband case. To validate the model, we implemented a numerical simulator and tested it with synthetic data. Numerical experiments demonstrate that the proposed model is computationally feasible, efficient, and compatible with realistic measurements and existing state-of-the-art simulators. The formulated model can be employed for analyzing how the involved parameters affect the generated beam pattern, and ultimately for optimizing measurement settings in an automatic and systematic way.
In ecology we may find scenarios where the same phenomenon (species occurrence, species abundance, etc.) is observed using two different types of samplers. For instance, species data can be collected from scientific surveys with a completely random sample pattern, but also from opportunistic sampling (e.g., whale or bird watching fishery commercial vessels), in which observers tend to look for a specific species in areas where they expect to find it. Species Distribution Models (SDMs) are a widely used tool for analyzing this kind of ecological data. Specifically, we have two models available for the above data: an independent model (IM) for the data coming from a complete random sampler and a dependent model (DM) for data from opportunistic sampling. In this work, we propose a sequential Bayesian procedure to connect these two models through the update of prior distributions. Implementation of the Bayesian paradigm is done through the integrated nested Laplace approximation (INLA) methodology, a good option to make inference and prediction in spatial models with high performance and low computational costs. This sequential approach has been evaluated by simulating several scenarios and comparing the results of sharing information from one model to another using different criteria. Our main results imply that, in general, it is better to share information from the independent (completely random) to the dependent model than the alternative way. However, it depends on different factors such as the spatial range or the spatial arrangement of sampling locations.
Blockchain-based IoT systems can manage IoT devices and achieve a high level of data integrity, security, and provenance. However, incorporating the existing consensus protocols in many IoT systems limits scalability and leads to high computational cost and network latency. We propose a hierar-chical and location-aware consensus protocol for IoI-blockchain applications inspired by the original Raft protocol to address these limitations. The proposed consensus protocol generates the consensus candidate groups based on nodes' individual reputation and distance information to elect the leader in each sub-layer blockchain and uses our threshold signature scheme to reach global consensus. Experimental results show that the proposed consensus protocol is scalable for large IoT applications and significantly reduces the communication cost, network latency, and agreement time by more than 50% compared with the Raft protocol for consensus processing.
Transport layer data leaks metadata unintentionally$\unicode{x2013}$such as who communicates with whom. While tools for strong transport layer privacy exist, they have adoption obstacles, including performance overheads incompatible with mobile devices. We posit that by changing the objective of metadata privacy for $\textit{all traffic}$, we can open up a new design space for pragmatic approaches to transport layer privacy. As a first step in this direction, we propose the $\textit{hybrid model}$, a system model that allows one to practically combine, and formally reason about network traffic with different privacy guarantees ($\textit{regular}$ and $\textit{deniable}$) in one joint system. Using techniques from information flow control we present a principled approach to construct a formal model and prove that deniable traffic achieves transport layer privacy against strong adversaries$\unicode{x2013}$this constitutes the first bridging of information flow control and anonymous communication to our knowledge. Additionally, we show that existing state-of-the-art protocols can be extended to support transport layer privacy, by designing a novel protocol for $\textit{deniable instant messaging}$ (DenIM), which is a variant of the Signal protocol. As an instantiation of the hybrid model, we implement and evaluate a proof-of-concept instant messaging system running both DenIM and regular Signal. We empirically show that the hybrid model can maintain low-latency for regular Signal traffic without breaking existing features, while at the same time supporting deniable Signal traffic.
In this paper, we develop a novel data-driven approach to accelerate solving large-scale linear equation systems encountered in scientific computing and optimization. Our method utilizes self-supervised training of a graph neural network to generate an effective preconditioner tailored to the specific problem domain. By replacing conventional hand-crafted preconditioners used with the conjugate gradient method, our approach, named neural incomplete factorization (NeuralIF), significantly speeds-up convergence and computational efficiency. At the core of our method is a novel message-passing block, inspired by sparse matrix theory, that aligns with the objective to find a sparse factorization of the matrix. We evaluate our proposed method on both a synthetic and a real-world problem arising from scientific computing. Our results demonstrate that NeuralIF consistently outperforms the most common general-purpose preconditioners, including the incomplete Cholesky method, achieving competitive performance across various metrics even outside the training data distribution.
The comprehension and adoption of Artificial Intelligence (AI) are beset with practical and ethical problems. This article presents a 5-level AI Capability Assessment Model (AI-CAM) and a related AI Capabilities Matrix (AI-CM) to assist practitioners in AI comprehension and adoption. These practical tools were developed with business executives, technologists, and other organisational stakeholders in mind. They are founded on a comprehensive conception of AI compared to those in other AI adoption models and are also open-source artefacts. Thus, the AI-CAM and AI-CM present an accessible resource to help inform organisational decision-makers on the capability requirements for (1) AI-based data analytics use cases based on machine learning technologies; (2) Knowledge representation to engineer and represent data, information and knowledge using semantic technologies; and (3) AI-based solutions that seek to emulate human reasoning and decision-making. The AI-CAM covers the core capability dimensions (business, data, technology, organisation, AI skills, risks, and ethical considerations) required at the five capability maturity levels to achieve optimal use of AI in organisations.
Game theory has by now found numerous applications in various fields, including economics, industry, jurisprudence, and artificial intelligence, where each player only cares about its own interest in a noncooperative or cooperative manner, but without obvious malice to other players. However, in many practical applications, such as poker, chess, evader pursuing, drug interdiction, coast guard, cyber-security, and national defense, players often have apparently adversarial stances, that is, selfish actions of each player inevitably or intentionally inflict loss or wreak havoc on other players. Along this line, this paper provides a systematic survey on three main game models widely employed in adversarial games, i.e., zero-sum normal-form and extensive-form games, Stackelberg (security) games, zero-sum differential games, from an array of perspectives, including basic knowledge of game models, (approximate) equilibrium concepts, problem classifications, research frontiers, (approximate) optimal strategy seeking techniques, prevailing algorithms, and practical applications. Finally, promising future research directions are also discussed for relevant adversarial games.
Bid optimization for online advertising from single advertiser's perspective has been thoroughly investigated in both academic research and industrial practice. However, existing work typically assume competitors do not change their bids, i.e., the wining price is fixed, leading to poor performance of the derived solution. Although a few studies use multi-agent reinforcement learning to set up a cooperative game, they still suffer the following drawbacks: (1) They fail to avoid collusion solutions where all the advertisers involved in an auction collude to bid an extremely low price on purpose. (2) Previous works cannot well handle the underlying complex bidding environment, leading to poor model convergence. This problem could be amplified when handling multiple objectives of advertisers which are practical demands but not considered by previous work. In this paper, we propose a novel multi-objective cooperative bid optimization formulation called Multi-Agent Cooperative bidding Games (MACG). MACG sets up a carefully designed multi-objective optimization framework where different objectives of advertisers are incorporated. A global objective to maximize the overall profit of all advertisements is added in order to encourage better cooperation and also to protect self-bidding advertisers. To avoid collusion, we also introduce an extra platform revenue constraint. We analyze the optimal functional form of the bidding formula theoretically and design a policy network accordingly to generate auction-level bids. Then we design an efficient multi-agent evolutionary strategy for model optimization. Offline experiments and online A/B tests conducted on the Taobao platform indicate both single advertiser's objective and global profit have been significantly improved compared to state-of-art methods.
Generative Adversarial Nets (GAN) have received considerable attention since the 2014 groundbreaking work by Goodfellow et al. Such attention has led to an explosion in new ideas, techniques and applications of GANs. To better understand GANs we need to understand the mathematical foundation behind them. This paper attempts to provide an overview of GANs from a mathematical point of view. Many students in mathematics may find the papers on GANs more difficulty to fully understand because most of them are written from computer science and engineer point of view. The aim of this paper is to give more mathematically oriented students an introduction to GANs in a language that is more familiar to them.
Knowledge graphs capture structured information and relations between a set of entities or items. As such they represent an attractive source of information that could help improve recommender systems. However existing approaches in this domain rely on manual feature engineering and do not allow for end-to-end training. Here we propose knowledge-aware graph neural networks with label smoothness regularization to provide better recommendations. Conceptually, our approach computes user-specific item embeddings by first applying a trainable function that identifies important knowledge graph relationships for a given user. This way we transform the knowledge graph into a user-specific weighted graph and then applies a graph neural network to compute personalized item embeddings. To provide better inductive bias, we use label smoothness, which assumes that adjacent items in the knowledge graph are likely to have similar user relevance labels/scores. Label smoothness provides regularization over edge weights and we prove that it is equivalent to a label propagation scheme on a graph. Finally, we combine knowledge-aware graph neural networks and label smoothness and present the unified model. Experiment results show that our method outperforms strong baselines in four datasets. It also achieves strong performance in the scenario where user-item interactions are sparse.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191