Ricci Curvature-Based Semi-Supervised Learning on an Attributed Network

In recent years, on the basis of drawing lessons from traditional neural network models, people have been paying more and more attention to the design of neural network architectures for processing graph structure data, which are called graph neural networks (GNN). GCN, namely, graph convolution networks, are neural network models in GNN. GCN extends the convolution operation from traditional data (such as images) to graph data, and it is essentially a feature extractor, which aggregates the features of neighborhood nodes into those of target nodes. In the process of aggregating features, GCN uses the Laplacian matrix to assign different importance to the nodes in the neighborhood of the target nodes. Since graph-structured data are inherently non-Euclidean, we seek to use a non-Euclidean mathematical tool, namely, Riemannian geometry, to analyze graphs (networks). In this paper, we present a novel model for semi-supervised learning called the Ricci curvature-based graph convolutional neural network, i.e., RCGCN. The aggregation pattern of RCGCN is inspired by that of GCN. We regard the network as a discrete manifold, and then use Ricci curvature to assign different importance to the nodes within the neighborhood of the target nodes. Ricci curvature is related to the optimal transport distance, which can well reflect the geometric structure of the underlying space of the network. The node importance given by Ricci curvature can better reflect the relationships between the target node and the nodes in the neighborhood. The proposed model scales linearly with the number of edges in the network. Experiments demonstrated that RCGCN achieves a significant performance gain over baseline methods on benchmark datasets.     

Transport Efficiency of Continuous-Time Quantum Walks on Graphs

Continuous-time quantum walk describes the propagation of a quantum particle (or an excitation) evolving continuously in time on a graph. As such, it provides a natural framework for modeling transport processes, e.g., in light-harvesting systems. In particular, the transport properties strongly depend on the initial state and specific features of the graph under investigation. In this paper, we address the role of graph topology, and investigate the transport properties of graphs with different regularity, symmetry, and connectivity. We neglect disorder and decoherence, and assume a single trap vertex that is accountable for the loss processes. In particular, for each graph, we analytically determine the subspace of states having maximum transport efficiency. Our results provide a set of benchmarks for environment-assisted quantum transport, and suggest that connectivity is a poor indicator for transport efficiency. Indeed, we observe some specific correlations between transport efficiency and connectivity for certain graphs, but, in general, they are uncorrelated.     

Stability and dynamical properties of material flow systems on random networks

The theory of complex networks and of disordered systems is used to study the stability and dynamical properties of a simple model of material flow networks defined on random graphs. In particular we address instabilities that are characteristic of flow networks in economic, ecological and biological systems. Based on results from random matrix theory, we work out the phase diagram of such systems defined on extensively connected random graphs, and study in detail how the choice of control policies and the network structure affects stability. We also present results for more complex topologies of the underlying graph, focussing on finitely connected Erdös-Réyni graphs, Small-World Networks and Barabási-Albert scale-free networks. Results indicate that variability of input-output matrix elements, and random structures of the underlying graph tend to make the system less stable, while fast price dynamics or strong responsiveness to stock accumulation promote stability.     

Modeling and simulations of the cascading failure of multiple interdependent R&D networks under risk propagation

In this paper, we study the robustness of multiple interrelated R&D networks under risk propagation. Firstly, using a bi-partite graph to represent the interrelated R&D networks is emphasized and proposed. Secondly, a risk propagation model is built by defining risk load and risk capacity of each enterprise on a specific R&D network, Thirdly, we use simulations to study risk propagation in interrelated R&D networks. Our results indicate that there exist three critical thresholds to quantify the robustness of R&D networks. Risk propagation in R&D networks is highly affected by the heterogeneity of all enterprises' scales and risk capacities.     

基于卷积神经网络的焊缝缺陷图像分类研究

为有效地对焊缝缺陷进行分类，从而判断焊接质量的等级，对传统卷积神经网络进行改进，提出一种多尺度压缩激励网络模型（SINet）。将4组两两串联的3×3卷积模块与Inception模块、压缩激励模块（SE block）相结合。通过多尺度压缩激励模块（SI module）将卷积层中的特征进行多尺度融合和特征重标定以提高分类准确率，并用全局平均池化层代替全连接层减少模型参数。此外考虑到焊接缺陷数量不平衡对准确率的影响，采用深度卷积对抗生成网络（DCGAN）进行数据集的平衡处理，并在该数据集上验证模型的有效性。与传统卷积神经网络相比，该模型具有良好的性能，在测试集上准确率达到96.77%，同时模型的参数个数也明显减少。结果表明该方法对焊缝缺陷图像能进行有效地分类。     

A Quantum Walk Model for Idea Propagation in Social Network and Group Decision Making

We propose a quantum walk model to investigate the propagation of ideas in a network and the formation of agreement in group decision making. In more detail, we consider two different graphs describing the connections of agents in the network: the line graph and the ring graph. Our main interest is to deduce the dynamics for such propagation, and to investigate the influence of compliance of the agents and graph structure on the decision time and the final decision. The methodology is based on the use of control-U gates in quantum computing. The original state of the network is used as controller and its mirrored state is used as target. The state of the quantum walk is the tensor product of the original state and the mirror state. In this way, the proposed quantum walk model is able to describe asymmetric influence between agents.     

Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics

The minimal dominating set for a digraph (directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erdös-Rényi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following. (i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one. (ii) We determine the ground state energy and the transition point of the Erdös-Rényi random graph. (iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.     

Network synchronizability analysis: The theory of subgraphs and complementary graphs

In this paper, subgraphs and complementary graphs are used to analyze network synchronizability. Some sharp and attainable bounds are derived for the eigenratio of the network structural matrix, which characterizes the network synchronizability, especially when the network’s corresponding graph has cycles, chains, bipartite graphs or product graphs as its subgraphs.     

Enhancing network lifespan in wireless sensor networks using deep learning based Graph Neural Network

Inadequate energy of sensors is one of the most significant challenges in the development of a reliable wireless sensor network (WSN) that can withstand the demands of growing WSN applications. Implementing a sleep-wake scheduling scheme while assigning data collection and sensing chores to a dominant group of awake sensors while all other nodes are in a sleep state seems to be a potential way for preserving the energy of these sensor nodes. When the starting energy of the nodes changes from one node to another, this issue becomes more difficult to solve. The notion of a dominant set-in graph has been used in a variety of situations. The search for the smallest dominant set in a big graph might be time-consuming. Specifically, we address two issues: first, identifying the smallest possible dominant set, and second, extending the network lifespan by saving the energy of the sensors. To overcome the first problem, we design and develop a deep learning-based Graph Neural Network (DL-GNN). The GNN training method and back-propagation approach were used to train a GNN consisting of three networks such as transition network, bias network, and output network, to determine the minimal dominant set in the created graph. As a second step, we proposed a hybrid fixed-variant search (HFVS) method that considers minimal dominant sets as input and improves overall network lifespan by swapping nodes of minimal dominating sets. We prepared simulated networks with various network configurations and modeled different WSNs as undirected graphs. To get better convergence, the different values of state vector dimensions of the input vectors are investigated. When the state vector dimension is 3 or 4, minimum dominant set is recognized with high accuracy. The paper also presents comparative analyses between the proposed HFVS algorithm and other existing algorithms for extending network lifespan and discusses the trade-offs that exist between them. Lifespan of wireless sensor network, which is based on the dominant set method, is greatly increased by the techniques we have proposed.     

基于广义回归神经网络的强干扰下垂直阵 目标距离估计方法*

以声压场采样协方差矩阵为特征,基于广义回归神经网络(Generalized Regression Neural Network,GRNN)研究强干扰下的水下声源测距问题,提出了优化扩展因子的方法以提高神经网络定位性能。本文利用仅有一个网络参数的GRNN,使用SWellEX-96实验S59航次的垂直阵数据,比较了以传统匹配场处理(Matched Field Processing,MFP)为代表的模型驱动方法和以CNN(Convolutional Neural Networks,CNN)、GRNN为代表的数据驱动方法在强干扰下的水下目标被动定位性能。结果表明,基于优化扩展因子的GRNN网络在强干扰下可以有效实现距离估计。     

Stability of weighted spectral distribution in a pseudo tree-like network model

The comparison of networks with different orders strongly depends on the stability analysis of graph features in evolving systems. In this paper, we rigorously investigate the stability of the weighted spectral distribution(i.e., a spectral graph feature) as the network order increases. First, we use deterministic scale-free networks generated by a pseudo treelike model to derive the precise formula of the spectral feature, and then analyze the stability of the spectral feature based on the precise formula. Except for the scale-free feature, the pseudo tree-like model exhibits the hierarchical and small-world structures of complex networks. The stability analysis is useful for the classification of networks with different orders and the similarity analysis of networks that may belong to the same evolving system.     

结合可视图的多状态交通流时间序列特性分析

交通流时间序列的研究主要采用数据挖掘和机器学习的方法,这些"黑箱"挖掘方法很难直观反映序列特性.为增强交通流时间序列及其特征分析的可视化性,结合可视图理论来构建交通流时间序列的关联网络,从复杂网络角度实现交通流时间序列的特性分析.在网络构建的过程中,考虑到不同交通状态下交通流表征具有的差异性,首先利用交通流参量的相关性对交通流状态进行分类,然后构建不同交通状态下的时间序列复杂网络,并对这些网络的特征属性给出统计分析,如度分布、聚类系数、网络直径、模块化等.研究表明,可视图法可为交通流时间序列映射到网络提供有效途径,并且不同状态下交通流时间序列构建的复杂网络的模块化、聚类系数和度分布等统计特征呈现一定的变化规律,为交通流运行态势的研究提供了可视化的分析角度.     

Efficient Network Dismantling via Node Explosive Percolation

The network dismantling problem asks the minimum separate node set of a graph whose removal will break the graph into connected components with the size not larger than the one percentage of the original graph.This problem has attracted much attention recently and a lot of algorithms have been proposed. However, most of the network dismantling algorithms mainly focus on which nodes are included in the minimum separate set but overlook how to order them for removal, which will lead to low general efficiency during the dismantling process. In this paper,we reformulate the network dismantling problem by taking the order of nodes' removal into consideration. An efficient dismantling sequence will break the network quickly during the dismantling processes. We take the belief-propagation guided decimation(BPD) dismantling algorithm, a state-of-the-art algorithm, as an example, and employ the node explosive percolation(NEP) algorithm to reorder the early part of the dismantling sequence given by the BPD. The proposed method is denoted as the NEP-BPD algorithm(NBA) here. The numerical results on Erd¨os-R′enyi graphs,random-regular graphs, scale-free graphs, and some real networks show the high general efficiency of NBA during the entire dismantling process. In addition, numerical computations on random graph ensembles with the size from 2~(10) to2~(19) exhibit that the NBA is in the same complexity class with the BPD algorithm. It is clear that the NEP method we used to improve the general efficiency could also be applied to other dismantling algorithms, such as Min-Sum algorithm,equal graph partitioning algorithm and so on.     

Quantifying complex patterns of bioacoustic variation: use of a neural network to compare killer whale (Orcinus orca) dialects

A quantitative measure of acoustic similarity is crucial to any study comparing vocalizations of different species, social groups, or individuals. The goal of this study was to develop a method of extracting frequency contours from recordings of pulsed vocalizations and to test a nonlinear index of acoustic similarity based on the error of an artificial neural network at classifying them. Since the performance of neural networks depends on the amount of consistent variation in the training data, this technique can be used to assess such variation from samples of acoustic signals. The frequency contour extraction and the neural network index were tested on samples of one call type shared by nine social groups of killer whales. For comparison, call similarity was judged by three human subjects in pairwise classification tasks. The results showed a significant correlation between the neural network index and the similarity ratings by the subjects. Both measures of acoustic similarity were significantly correlated with the groups' association patterns, indicating that both methods of quantifying acoustic similarity are biologically meaningful. An index based on neural network analysis therefore represents an objective and repeatable means of measuring acoustic similarity, and allows comparison of results across studies, species and time.     

无线传感器网络中基于最小延时的数据汇集树构建与传输调度算法

无线传感器网络的数据通信模式问题是目前的研究热点,针对现有的无线传感器网络数据汇集算法延时较大这一不足,对最小延时数据汇集树和传输调度问题进行了研究。提出一种基于度约束的汇集树构建算法(DCAT)。该算法按照 BFS 方式遍历图,当遍历到每个节点时,通过确定哪些节点与汇点更近来确定潜在母节点集合。然后,选择图中度数最小的潜在母节点作为当前被遍历节点的母节点。此外,为了在给定的汇集树上进行高效地数据汇集,还提出两种新的基于贪婪的TDMA传输调度算法：WIRES-G 和 DCAT-Greedy。利用随机生成的不同规模的传感器网络,参照当前最新算法,对文中方法的性能进行了全面评估。结果表明,与当前最优算法相比,文中调度算法与文中汇集树构建算法结合起来,可显著降低数据汇集的延时。     

基于一维元胞自动机的复杂网络恶意软件传播研究

基于一维元胞自动机,研究复杂网络恶意软件传播行为.利用信息网络节点全局交互的特点,建立元胞自动机邻域和状态转换函数,提出恶意软件传播模型,研究在多种网络拓扑下恶意软件传播的概率行为.研究表明,该模型能够准确描述在最近邻耦合网络（nearest-neighbor coupled network, NC）,Erdos-Renyi（ER）随机网络,Watts-Strogatz（WS） 小世界网络和Barabasi-Albert（BA）幂率网络等拓扑下的传播动力学行为,不仅能反映恶意软件传播的平均趋势,而且可以描述病毒消亡和渗透等稀有概率事件,有效克服基于平均场方法建立的微分方程模型只能反映传播的平均趋势,只适合对传播作整体预测的局限性.同时,研究指出网络中度分布的异质化程度和网络的局域空间交互特征是影响传播及免疫行为的关键要素. 关键词： 复杂网络 恶意软件传播 元胞自动机 状态转换函数     

An Efficient Partition-Based Approach to Identify and Scatter Multiple Relevant Spreaders in Complex Networks

One of the main problems in graph analysis is the correct identification of relevant nodes for spreading processes. Spreaders are crucial for accelerating/hindering information diffusion, increasing product exposure, controlling diseases, rumors, and more. Correct identification of spreaders in graph analysis is a relevant task to optimally use the network structure and ensure a more efficient flow of information. Additionally, network topology has proven to play a relevant role in the spreading processes. In this sense, more of the existing methods based on local, global, or hybrid centrality measures only select relevant nodes based on their ranking values, but they do not intentionally focus on their distribution on the graph. In this paper, we propose a simple yet effective method that takes advantage of the underlying graph topology to guarantee that the selected nodes are not only relevant but also well-scattered. Our proposal also suggests how to define the number of spreaders to select. The approach is composed of two phases: first, graph partitioning; and second, identification and distribution of relevant nodes. We have tested our approach by applying the SIR spreading model over nine real complex networks. The experimental results showed more influential and scattered values for the set of relevant nodes identified by our approach than several reference algorithms, including degree, closeness, Betweenness, VoteRank, HybridRank, and IKS. The results further showed an improvement in the propagation influence value when combining our distribution strategy with classical metrics, such as degree, outperforming computationally more complex strategies. Moreover, our proposal shows a good computational complexity and can be applied to large-scale networks.     

Automatic generation of min-weighted persistent formations

This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating min-weighted rigid and min-weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.     

Minimum Spanning vs. Principal Trees for Structured Approximations of Multi-Dimensional Datasets

Construction of graph-based approximations for multi-dimensional data point clouds is widely used in a variety of areas. Notable examples of applications of such approximators are cellular trajectory inference in single-cell data analysis, analysis of clinical trajectories from synchronic datasets, and skeletonization of images. Several methods have been proposed to construct such approximating graphs, with some based on computation of minimum spanning trees and some based on principal graphs generalizing principal curves. In this article we propose a methodology to compare and benchmark these two graph-based data approximation approaches, as well as to define their hyperparameters. The main idea is to avoid comparing graphs directly, but at first to induce clustering of the data point cloud from the graph approximation and, secondly, to use well-established methods to compare and score the data cloud partitioning induced by the graphs. In particular, mutual information-based approaches prove to be useful in this context. The induced clustering is based on decomposing a graph into non-branching segments, and then clustering the data point cloud by the nearest segment. Such a method allows efficient comparison of graph-based data approximations of arbitrary topology and complexity. The method is implemented in Python using the standard scikit-learn library which provides high speed and efficiency. As a demonstration of the methodology we analyse and compare graph-based data approximation methods using synthetic as well as real-life single cell datasets.     

Bogoliubov de Gennes equation on metric graphs

We consider Bogoliubov de Gennes equation on metric graphs. The vertex boundary conditions providing self-adjoint realization of the Bogoliubov de Gennes operator on a metric star graph are derived. Secular equation providing quantization of the energy and the vertex transmission matrix are also obtained. Application of the model for Majorana wire networks is discussed.