- : encoding, decoding and causal relationships;
- isovariable hypergraph diffusion neural operator;
- subgraph frequency distribution estimates using graph neural networks;
- network bypass maintains complexity;
- network completion time; tropical approximation of the completion time of the active network;
- personalized recommendation system based on social relations and historical behavior;
- characterizes nodes and edges in dynamic attribute networks: a society-based approach;
- Reward sharing relationship network in multiagent reinforcement learning as a framework for emergency behavior;
- Acceleration dynamics of general non-local traffic flow models Monte Carlo method;
- Behavior changes during the pandemic deteriorate the income diversity encountered by cities;
- Personalization with bounded sensitivity PageRank performs differential private graph learning;
- as a rebellion of complex networks: image co-appearance and hierarchy in PKK;
- core-marginal community structure;
- spin glass system as collective active reasoning;
- equity-driven taxi pricing strategy based on dual auction mechanism in the urban area of Bangkok, Thailand;
- detects people interested in non-suicide self-harm on social media;
analytical relationships between complex networks: encoding, decoding and causal relationships
original title: Analytic relationships Between complex networks: encoding, decoding, and causeality
Address: http://arxiv.org/abs/2207.06606
Author: Yang Tian, Hedong Hou, Guangzheng Xu, Yaoyuan Wang, Ziyang Zhang, Pei Sun
Abstract: Complex networks are very common in physics, biology, computer science and social sciences. Quantifying the relationships between complex networks paves the way for understanding the potential information sharing across networks. However, basic relationship metrics between complex networks, such as information divergence, mutual information, Fisher information, and causality, are not well defined. As a trade-off, common strategies (e.g., network embedding, matching, and kernel methods) measure network relationships in a data-driven manner. These methods are computationally oriented and are not suitable for analytical derivation in mathematics and physics. To solve these problems, we propose a theory to deduce the best representation of attributes of network topology. Our theory shows that complex networks can be fully represented by the Gauss Markov random field defined by the discrete Schr”odinger operator, satisfying both the required smoothness and maximum entropy properties. Based on this representation, we can analyze and measure the relationship between different networks in terms of topology properties. As an illustration, we mainly show how to define encoding (e.g., divergence of information and mutual information), decoding (e.g., Fisher information), and causality (e.g., transfer entropy and Granger causality). We validate our framework on representative complex networks (e.g., evolutionary stochastic network models, protein-protein interaction networks, and compound networks) and demonstrate a range of scientific and engineering challenges (e.g., network evolution, clustering, and classification) It can be solved from a new perspective. The computationally effective implementation of our theory is related as an open source toolbox.
isovariant hypergraph diffusion neural operator
Original title: Equivariant Hypergraph Diffusion Neural Operators
Address: http://arxiv.org/abs/2207.06680
Author: Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, Pan Li
Abstract: Hypergraph neural networks (HNNs) that encode hypergraphs using neural network provide a promising approach to modeling higher-order relationships in the data and further addressing related prediction tasks based on such higher-order relationships. However, higher-order relationships in practice contain complex patterns and are often highly irregular. Therefore, it is often challenging to design an HNN that is sufficient to express these relationships while maintaining computational efficiency.Inspired by the hypergraph diffusion algorithm, this work proposes a new HNN architecture called ED-HNN that proves to represent any continuous isovariable hypergraph diffusion operator that can model various higher order relationships. ED-HNN can be effectively implemented by combining star expansion of hypergraphs with standard messaging neural networks. ED-HNN further shows great advantages in handling heterophilic hypergraphs and building depth models. We evaluate the node classification of ED-HNN on nine real-world hypergraph datasets. ED-HNN outperforms the optimal baseline on all nine datasets and achieves prediction accuracy of more than 2% uparrow on four of these datasets.
Estimation of subgraph frequency distribution of graph neural networks
Original title: Subgraph Frequency Distribution Estimation using Graph Neural Networks
Address: http://arxiv.org/abs/2207.06684
Author: Zhongren Chen, Xinyue Xu, Shengyi Jiang, Hao Wang, Lu Mi
Abstract: Graphlets are important features that describe the basic units of large networks. The calculation of sub-graph frequency distribution has a wide range of applications in many fields such as biology and engineering. Unfortunately, due to the inherent complexity of this task, most existing methods are computationally intensive and inefficient. In this work, we propose GNNS, a novel representation learning framework that utilizes graph neural networks to efficiently sample subgraphs to estimate their frequency distribution. Our framework includes an inference model and a generative model for learning hierarchical embeddings of nodes, subgraphs, and graph types. Subgraphs are sampled in a highly scalable and parallel manner using learned models and embeddings, and then frequency distribution estimation is performed based on these sampled subgraphs. Ultimately, our approach achieves considerable accuracy and three orders of magnitude faster than existing approaches.
Network bypass maintains complexity
Original title: Network bypasses sustain complexity
Address: http://arxiv.org/abs/2207.06813
Author: Ernesto Estrada, Lucas Lacasa
Abstract: The real world network is neither regular nor random, and mechanisms such as the Watts-Strrogatz or the Barabasi-Albert model elegantly explain this fact. These two mechanisms will naturally create shortcuts and hub , thereby enhancing the navigation of the network. They are often overused during the ground line navigation process, making the network susceptible to interference. So, why are networks with complex topology everywhere? Here we show these models entropy-generating network bypasses: alternative routes for shortest paths are topologically longer but easier to navigate. We developed a mathematical theory that elucidates the emergence and integration of network bypasses and measures their navigation gains. We apply our theory to a wide range of real-world networks and find that they maintain complexity through different numbers of network bypasses. At the top of this complexity ranking, we find the human brain, which points out the importance of these results in understanding the plasticity of complex systems.
Tropical approximation of activity network completion time
Original title: Tropical approximation to finish time of activity networks
Address: http://arxiv.org/abs/2203.04621
Author: Alexei Vazquez
Abstract: We decompose complex projects into activities and their logical dependencies. We estimate project completion time based on activity duration and relationship. However, adverse event triggers delayed cascade change completion time. Here, I deduce the tropical algebraic equation of the completion time of the active network, encapsulating the exogenous perturbation linear superposition principle in the tropical sense. From tropical algebraic equations, I derive the completion time distribution and explicitly refer to the distribution of exogenous delays as well as network topology and geometry .
Personalized recommendation system based on social relations and historical behaviors
Original title: Personalized recommendation system based on social relations and historical behaviors
Address: http://arxiv.org/abs/2206.13072
Author: Yan-Li Lee, Tao Zhou, Kexin Yang, Yajun Du, Liming Pan
Abstract: Previous research has shown that recommendation algorithms based on user historical behavior can provide satisfactory recommendation performance. Many of these algorithms focus on user interests and ignore the impact of social relations on user behavior. Social relations not only carry intrinsic information about similar consumer tastes or behaviors, but also imply the influence of an individual on his neighbors. In this article, we assume that the user's social relations and historical behavior are related to the same factors. Based on this assumption, we propose an algorithm that focuses on social relations useful to the recommendation system through mutual constraints from two types of information. We test the performance of our algorithm on four types of users, including all users, active users, inactive users, and cold start users. The results show that in four scenarios affected by recommended accuracy and diversity indicators, the proposed algorithm is better than the benchmark. We further designed a randomization model to explore the contribution of social relations to recommendation performance, and the results show that the contribution of social relations in the proposed algorithm depends on the coupling strength of social relations and historical behavior.
Characterizes nodes and edges in dynamic attribute networks: a society-based method
Original title: Characterizing Nodes and Edges in Dynamic Attributed Networks: A Social-based Approach
Address: http://arxiv.org/abs/2207.07035
Author: Thiago H. P. Silva, Alberto H. F. Laender, Pedro O. S. Vaz de Melo
Abstract: How to characterize nodes and edges in dynamic attribute network based on social aspects? We address this problem by exploring the strength of the connections among participants over time and their associated attributes, thereby capturing the participants’ social roles and the significance of their dynamic interactions in different social network scenarios. To this end, we apply social concepts to promote a better understanding of the potential complexity involving participants and their social motivations . More specifically, we use the concept of brokerage, the ability to create bridges with multiple patterns and the ability to close, aggregate the ability modes with similar nodes. Therefore, we reveal differences in social interactions across academic co-authoring networks and question-and-answer communities. We also verified our social definition through network attribute statistics, taking into account the importance of nodes and edges in social structures.
Reward sharing relationship network in multi-agent reinforcement learning as a framework for emergency behavior
Original title: Reward-Sharing Relational Networks in Multi-Agent Reinforcement Learning as a Framework for Emergent Behavior
Address: http://arxiv.org/abs/2207.05886
Author: Hossein Haeri, Reza Ahmadzadeh, Kshitij Jerath
Summary: In this work, we integrate “social” interactions into MARL settings through a user-defined relationship network and examine the impact of subject-subject relationships on the rise of emergency behavior. Using the insights from sociology and neuroscience , our proposed framework modeled subject relations using the concept of reward-shared relationship network (RSRN), where network edge weights are used as a measure of a subject's success (or "care") others. We construct relationship rewards as a function of RSRN interaction weights to jointly train multiagent systems through the multiagent reinforcement learning algorithm. The performance of the system is tested for 3-agent scenarios with different relational network structures (e.g., self-interested networks, community networks, and authoritative networks). Our results show that reward-sharing relationship networks can significantly affect learning behavior. We hypothesized that RSRN can serve as a framework where different relational networks produce different urgent behaviors, often similar to an intuitive sociological understanding of such networks.
Acceleration dynamics of general nonlocal traffic flow model
Original title: Accelerated Kinetic Monte Carlo methods for general nonlocal traffic flow models
Address: http://arxiv.org/abs/2207.06493
Author: Yi Sun, Changhui Tan
Abstract: This article proposes a class of one-dimensional cellular automata (CA) models about traffic flow, which have the characteristics of nonlocal prospective interaction. We developed the Kinetics Monte Carlo (KMC) algorithm to simulate dynamics. The standard KMC approach may be inefficient for models with global interactions. We designed an accelerated KMC method to reduce the computational complexity of evaluating non-local conversion rates. We studied several numerical experiments to demonstrate the efficiency of the acceleration algorithm and obtained a basic dynamic diagram of the various parameter settings.
Behavioral changes during the pandemic worsened income diversity of urban encounters
Original title: Behavioral changes during the pandemic worsened income diversity of urban encounters
Address: http://arxiv.org/abs/2207.06895
Author: Takahiro Yabe, Bernardo Garcia Bulle Bueno, Xiaowen Dong, Alex `Sandy’ Pentland, Esteban Moro
Abstract: It is well known that the diversity of physical contact and social interaction in urban environments can stimulate economic productivity and innovation in cities, while also promoting the resilience of social capital and communities. However, travel restrictions during the pandemic have forced people to drastically reduce physical contact in cities, which has raised questions about the social impact of such behavioral changes. In this article, we use a large-scale privacy-enhanced mobile dataset of more than one million anonymous mobile phone users in four major U.S. cities to examine how the income diversity encountered in cities during different periods throughout the pandemic changed for three years before and during the pandemic. We found that the diversity experienced by cities has dropped significantly during the pandemic (down 15% to 30%) and continues until the end of 2021, although overall liquidity indicators have returned to pre-pandemic levels. Counterfactual analysis shows that while a decrease in outdoor activities (a higher stay-at-home ratio) in the early stages of the pandemic was a major factor in the decline in diversity, behavioral changes, including a lower willingness to explore new places and further changes in visiting preferences, worsened the long-term diversity encountered. Our findings suggest that the pandemic may have a long-term negative impact on urban income diversity and provide implications for the trade-off between the strictness of our policies to manage COVID-19 after the pandemic and the diversity encountered in cities.
Differentialized PageRank for differential private graph learning through bounded sensitivity
Original title: Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Address: http://arxiv.org/abs/2207.06944
Author: Alessandro Epasto, Vahab Mirrokni, Bryan Perozzi, Anton Tsitsulin, Peilin Zhong
Abstract: Personalized PageRank (PPR) is a basic tool for unsupervised learning graph representation, such as node ranking, tags and graph embedding. However, while data privacy is one of the most important issues lately, existing PPR algorithms are not designed to protect user privacy. PPR is highly sensitive to edges of the input graph: the difference in only one edge may cause large changes in the PPR vector, which may reveal private user data. In this work, we propose an algorithm that outputs an approximate PPR and has proven finite sensitivity to the input edges. Furthermore, we demonstrate that when the degrees of the input graph are large, our algorithm can achieve similar accuracy as that of the non-private algorithm. Our bounded sensitivity PPR directly implies private algorithms for several graph learning tools, such as differential private (DP) PPR ranking, DP node classification, and DP node embedding. To supplement our theoretical analysis, we also empirically verified the actual performance of our algorithm .
As a complex network: image co-appearance and hierarchy in PKKK
Original title: Insurgency as Complex Network: Image Co-Appearance and Hierarchy in the PKK
Address: http://arxiv.org/abs/2207.06946
Author: Ollie Ballinger
Abstract: Although people are increasingly aware of the importance of insurgent organizational structures to conflict results, there are few empirical studies on this. While the root of this problem is that data from radical organizational structures is inaccessible, insurgents often publish large amounts of image data on the Internet. In this article, I developed a new approach to leverage this rich but underutilized data source by automatically creating social network maps based on co-appearance in photos using deep learning. Using 19,115 obituary images published online by Turkish Kurdish armed group PKK, I demonstrate that individuals’ centrality in the resulting co-appearance network is closely related to their ranking in insurgent organizations.
Core-Border Community Structure
Original title: Structure of Core-Periphery Communities
Address: http://arxiv.org/abs/2207.06964
Author: Junwei Su, Peter Marbach
Abstract: Experiments show that communities in social networks often have core-peripheral topology. However, there is still a lack of understanding of the precise structure of core-peripheral communities in social networks, including the rate of interaction between the connecting structure and the subject. In this article, we use the game theory method to more accurately describe the structure of the core-peripheral community.
spin glass system as collective active reasoning
Original title: Spin glass systems as collective active inference
Address: http://arxiv.org/abs/2207.06970
Author: Conor Heins, Brennan Klein, Daphne Demekas, Miguel Aguilera, Christopher Buckley
Abstract: An open question in the study of emergency behavior in multiagent Bayesian systems is the relationship (if any) between individual and collective reasoning. In this paper, we explore the correspondence between generative models present on two different scales, using the rotating glass model as a sandbox system to study this problem. We show that the collective dynamics of a particular type of active inference subject are equivalent to sampling from the static distribution of a spin-glass system. Thus, a set of specially designed active inference subjects can be described as implementing a sampling-based form of inference (i.e., from a Boltzmann machine) at a higher level. However, this equivalence is very fragile and requires simple modifications to the generative model of individual subjects or their interactive properties. We discuss the implications of this correspondence and its vulnerability to the study of multi-scale systems composed of Bayesian subjects.
The feasibility of equity-driven taxi pricing strategy based on the dual auction mechanism in the Bangkok metropolitan area of Thailand
Original title: Feasibility of Equity-driven Taxi Pricing Strategy based on Double Auction Mechanism in Bangkok Metropolitan Region, Thailand
Address: http://arxiv.org/abs/2207.06981
Author: He-in Cheong, Jonathan Sanz Carcelen, Manlika Sukitpaneenit, Panagiotis Angeloudis, Arnab Majumdar, Marc Stettler
Abstract: Taxi drivers’ refusal to passengers has affected travel behavior in many cities and suburban areas, often leaving potential customers in non-popular areas stranded and unable to take a taxi. To overcome this problem, many practices have been implemented, such as penalties for drivers, bans and new pricing strategies. This paper proposes a dual auction taxi fare scheme, which allows passengers and taxi drivers to jointly influence prices, and combines clustering methods to prevent strategic service rejection. Taking the Bangkok metropolitan area in Thailand as an example, the case study data is detailed and uneven taxi itinerary distribution. The dual auction mechanism is tailored to 2019 taxi travel, service rejection complaints and local travel behaviors to improve transportation equity.To measure the performance of the new dual auction program, a subject-based custom model of taxi service in the Bangkok metropolitan area was created at different rejection rates of 0%-20%. On the one hand, model the current rejection behavior, and on the other hand, apply a dual auction pricing strategy. The results show that the dual auction strategy produces accessibility of spatial distribution and results in a taxi allocation success rate of up to 30%. The dual auction program has increased pickup volumes of 10-15% at locations 20-40 km from downtown Bangkok, albeit in a low-profit area. The total air pollutant emissions from taxis increased by 10%, while local emissions in the central area of Bangkok have decreased by as much as 40%. Using an average surcharge of 5 baht, total revenue fell by 20%. The results show that fair-driven pricing strategies as an implementation of transportation policies will be beneficial.
Detecting people interested in non-suicidal self-harm on social media
Original title: Detecting People Interested in Non-Suicidal Self-Injury on Social Media
Address: http://arxiv.org/abs/2207.07014
Author: Zaihan Yang, Dmitry Zinoviev
Abstract: We propose a supervised learning method to detect people interested in non-suicidal self-harm (NSSI). We treat the task as a binary classification problem and build a classifier based on features extracted from people’s self-declared interests. An experimental evaluation of the real-world dataset LiveJournal social blog network platform demonstrates the effectiveness of our proposed model.
Statement: The copyright of the Arxiv article abstract belongs to the original author of the paper. It is corrected and sorted by me after machine translation. Please do not reprint it at will without permission. This series is updated simultaneously on the official account "NetSci Research Express" (netsci) and personal blogs.
