Search

The traditional method of searching transmission section generally has the problem of omission and time-consuming. A topology converging algorithm of power grid adjacency matrix is proposed in this paper. It aggregates neighboring buses based on a simple matrix transformation rule, and identify key transmission sections based on matrix operations and power flow distribution factors. This method has the advantage of no presetting the sub-zone, which can avoid the simplification of the grid topology in the sub-zone and improve the calculation accuracy. The complex logical operations of the traversal algorithm adopted by most of traditional methods can be avoided, and the calculation speed can be effectively improved. Besides, the algorithm also has a memory characteristic which can be applied to the online search of key transmission sections. The results of several IEEE test systems show the effectiveness of the proposed algorithm.

In this paper, the consensus problem for the first-order discrete-time multi-agent systems (MASs) In the presence of fault is studied. This study uses two concepts of watchdog model-based observer and weighted adjacency matrix approach (WAMA). The purpose of this study is to reach a consensus on MASs when one or more agents have been damaged. In this method, for any agent, a watchdog that measures the amount of difference between the states of the actual system and the calculated states of the system by the agent's model is designed, this generated residual declares the amount of agents deviation. A decision function is used to decide how this malfunctioning affects the neighboring agents. Therefore, the states that each agent transmits to the neighboring agents are augmented by the output of the decision function. By increasing states matrix dimensions, each agent will report its health status or commanding by using a new state to the neighboring agents. This additional state is affected by a decision function that expresses the neighboring agents how should behave with this malfunction agent. Finally, the produced residue will be weight of the adjacency matrix and will cause to correct consensus. Simulation results are presented to illustrate the effectiveness of this approach.

In this article, we analyze the limiting eigen-value distribution (LED) of random geometric graphs (RGGs). The RGG is constructed by uniformly distributing n nodes on the d-dimensional torus $\Gamma^{d}\equiv [0, 1]^{d}$ and connecting two nodes if their $\ell_{p}$-distance, $ p\in [1,\ \infty]$ is at most r n . In particular, we study the LED of the adjacency matrix of RGGs in the connectivity regime, in which the average vertex degree scales as $\log(n)$ or faster, i.e., $\Omega(\log(n))$. In the connectivity regime and under some conditions on the radius r n , we show that the LED of the adjacency matrix of RGGs converges to the LED of the adjacency matrix of a deterministic geometric graph (DGG) with nodes in a grid as n goes to infinity. Then, for n finite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG and provide an upper bound for the approximation error. Index Terms--Random geometric graphs, adjacency matrix, limiting eigenvalue distribution, Levy distance.

Community detection in network-type data provides a powerful tool in analyzing and understanding real-world systems. In fact, community detection approaches aim to reduce the network’s dimensionality and partition it into a set of disjoint clusters or communities. However, real networks are usually corrupted with noise or outliers which affect the detected community structure quality. In this paper, a new robust community detection algorithm that is capable of recovering a clean or a smoothed version of the corrupted graph and detecting the correct community structure is introduced. The proposed approach combines robust principal component analysis (RPCA) and symmetric nonnegative matrix factorization (SymNMF) in a single optimization problem. The proposed problem is solved under the framework of alternating direction methods of multipliers (ADMM). In particular, the corrupted adjacency matrix is decomposed into a low-rank and sparse components using RPCA and the community structure is detected by applying SymNMF to the extracted low-rank component. Extensive experiments that have been conducted on real and simulated binary and weighted networks show that the proposed approach significantly outperforms existing algorithms in detecting the correct community structure even in grossly corrupted networks.

Recently, graph embedding models significantly improved the quality of graph machine learning tasks, such as node classification and link prediction. In this work, we propose a model called JONNEE (JOint Network Nodes and Edges Embedding), which learns node and edge embeddings under self-supervision via joint constraints in a given graph and its edge-to-vertex dual representation as a Line graph. The model uses two graph autoencoders with additional structural feature engineering and several regularization techniques to train for an adjacency matrix reconstruction task in an unsupervised setting. Experimental results show that our model performs on par with state-of-the-art undirected attribute graph embedding models and requires less number of epochs to achieve the same quality due to Line graph self-supervision under a unified embedding framework.

Super-resolution mapping (SRM) is an effective technology to solve the problem of mixed pixels because it can be used to generate fine-resolution land cover maps from coarse-resolution remote sensing images. Current methods based on deep neural networks have been successfully applied to SRM, as they can learn complex spatial patterns from training data. However, they lack the ability to learn structural information between adjacent land cover classes, which is vital in the reconstruction of spatial distribution. In this article, an SRM method based on graph convolutional networks (GCNs), named ${\rm{SR}}{{\rm{M}}_{{\rm{GCN}}}}$, is proposed to improve SRM results by capturing structure information on the graph. In ${\rm{SR}}{{\rm{M}}_{{\rm{GCN}}}}$, a supervised inductive learning strategy with mini-graphs as input is considered, which is an extension of the GCN framework. Furthermore, two operations are designed in terms of adjacency matrix construction and an information propagation rule to help reconstruct detailed information of geographical objects. Experiments on three datasets with different spatial resolutions demonstrate the qualitative and quantitative superiority of ${\rm{SR}}{{\rm{M}}_{{\rm{GCN}}}}$ over three other popular SRM methods.

Reliable and accurate wind speed prediction has significant impact in many industrial sectors such as economic, business and management among others. This paper presents a new model for wind speed prediction based on Graph Attention Networks (GAT). In particular, the proposed model extends GAT architecture by equipping it with a learnable adjacency matrix as well as incorporating a new attention mechanism with the aim of obtaining attention scores per weather variable. The output of the GAT based model is combined with the LSTM layer in order to exploit both the spatial and temporal characteristics of the multivariate multidimensional historical weather data. Real weather data collected from several cities in Denmark and Netherlands are used to conduct the experiments and evaluate the performance of the proposed model. We show that in comparison to previous architectures used for wind speed prediction, the proposed model is able to better learn the complex input-output relationships of the weather data. Furthermore, thanks to the learned attention weights, the model provides an additional insights on the most important weather variables and cities for the studied prediction task., Comment: 8 pages, 5 figures

With the rapid growth of the Internet, the scale of graphs has increased dramatically, which poses special challenges in representing both web graphs and social network graphs. In the adjacency matrix of web and social network graphs, only a very small proportion of the elements is “1” s. Furthermore, we find that using the aggregation of scattered 1 s to form a high density of adjacency matrices is beneficial to the compression of storage space. Based on these findings, we propose the DGC-K2-tree compression approach based on K2-tree, which can greatly increase the density of 1 s among the existing algorithms and adequately compress the blank area in the adjacency matrix. Then, we design a query algorithm for this mechanism to support the operation on the graph. The experimental results show that compared with the state-of-the-art algorithms, including the K2-tree based on a diagonal clustering mechanism (K2-BDC), the K2-tree, Re-Pair, and LZ78, our approach achieves better compression ratio and shorter time consumption. In terms of storage efficiency, our approach reduces the space by an average of 34.07% compared to the best performing algorithm K2-BDC. In terms of query efficiency, our approach reduces the time by an average of 80.63% compared to the best performing algorithm LZ78.

Event detection is a particularly challenging problem in information extraction. The current neural network models have proved that dependency tree can better capture the correlation between candidate trigger words and related context in the sentence. However, syntactic information conveyed by the original dependency tree is insufficient for detecting trigger since the dependency tree obtained from natural language processing toolkits ignores semantic context information. Existing approaches employ a static graph structure based on original dependency tree which is incompetent in terms of distinguishing interrelations among trigger words and contextual words. So how to effectively make use of relevant information while ignoring irrelevant information from the dependency trees remains a challenging research question. To address this problem, we investigate a graph convolutional network over multiple latent context-aware graph structures to perform event detection. We exploit a multi-head attention mechanism on BERT representation and original adjacency matrix to generate multiple latent context-aware graph structures (a “dynamic cutting” strategy), which can automatically learn how to select the useful dependency information. Furthermore, we investigate graph convolutional networks with residual connections to combine the local and non-local contextual information. Experimental results on ACE2005 dataset show that our model achieves competitive performances compared with the methods based on dependency tree for event detection.

One of the main problems when developing graph-based applications is the availability of large and representative datasets. The lack of real graphs has motivated the development of software tools for generating synthetic graphs. R-MAT is a data generation method that was designed to produce synthetic graphs whose characteristics resemble those occurring in real networks. Although the generation model defined by R-MAT is easy to understand, its implementation is not trivial and it has intrinsic memory restrictions that makes the generation of very large graphs difficult. This paper studies the practical implementation of R-MAT. We discuss the issues of the original implementation which works with the adjacency matrix of the graph and analyze the size of the resulting graph obtained with the R-MAT model. Then, we introduce and experimentally evaluate R3MAT, an alternative implementation for R-MAT based on an array of degrees. These experiments show that $(i)$ our R3MAT is able to generate graphs of hundred million nodes and billion edges in a single machine, $(ii)$ our method preserves the characteristic power-law distribution of the edge degrees present in real-world graphs, and $(iii)~\text{R}^{3}$ MAT has the best performance in the current state of the art, when considering a single modest computer in a sequential fashion.

Path sequence selection is important for multimodal transport processes. AND/OR graphs (AOG) have been applied to describe practical multimodal transport route planning problems by using ‘AND’ and ‘OR’ matrices. An AOG-based multimodal transport route planning problem is an NP-hard combinatorial optimization problem. Heuristic evolution methods can be adopted to handle it. While adjacency (AND) relationship issues can be addressed, contradiction (OR) relations are not well addressed by existing multimodal transport route planning methods. Thus, an ineffective result may be obtained in practice. The OR matrix is a conflict matrix that describes the choice of mode of transport in the process of multimodal transport. By using a contradiction matrix together with an adjacency matrix and tabu list, an approach used in existing work, this paper proposes an effective triple-phase generate route method (TPGR) to produce a feasible multimodal transport path sequence based on an AOG. This paper uses energy consumption to evaluate the multimodal transport energy efficiency. The information entropy is applied to describe the risks of the transport process. The energy consumption and the information entropy lead to a novel dual-objective optimization model where route energy consumption and route risk are minimized. An improved ant colony algorithm is developed to effectively generate a set of Pareto solutions for route selection, which are used for the dual-objective multimodal transport route optimization problem. This methodology is applied to practical multimodal transport route selection processes on two maps to verify its effectiveness and feasibility.

Learning based hashing has been widely used in approximate nearest neighbor search for image retrieval. However, most of the existing hashing methods are designed to learn only simplex feature similarity while ignored the location similarity among multiple objects, thus cannot work well on multi-label image retrieval tasks. In this paper, we propose a novel supervised hashing method which fusions the two kinds of similarities together. First, we leverage an adjacency matrix to record the relative location relationship among multiple objects. Second, by incorporating matrix discretization difference and image label difference, we re-define the pairwise image similarity in a more meticulous way. Third, to learn more distinguishable hash codes, we leverage an attention sub-network to identify the approximate regions of the objects in an image so that the extracted features can mainly focus on the foreground objects and ignore the background clutter. The loss function in our method consists of a multi-categories classification loss which is used to learn the attention sub-network and a hash loss with a scaled sigmoid function which is used to learn the efficient hash codes. Experiment results show that our proposed method is effective in preserving high-level similarities and outperforms the baseline methods in multi-label image retrieval.

We provide a deterministic $\tilde{O}(\log N)$-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error ($\epsilon=1/\mathrm{poly}(N)$) where $N$ is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space $O(\log N)$ (following Aleliunas et al., FOCS 79) and by a deterministic algorithm using space $O(\log^{3/2} N)$ (Saks and Zhou, FOCS 95 and JCSS 99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible ($\epsilon=1/N^{\omega(1)}$), generalizing what Hoza and Zuckerman (FOCS 18) recently showed for the special case of distinguishing whether a random walk probability is $0$ or greater than $\epsilon$. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic $\tilde{O}(\log N)$-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS 17) that gave a deterministic $\tilde{O}(\log N)$-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS 19) that gave a randomized $\tilde{O}(N)$-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of "cycle-lifted graphs", where we take a graph and "lift" it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one)., Comment: 52 pages. Fixed a bug in Lemma 5.8 that affected Theorem 5.9

Motivated by the prevalent data science applications of processing and mining large-scale graph data such as social networks, web graphs, and biological networks, as well as the high I/O and communication costs of storing and transmitting such data, this paper investigates lossless compression of data appearing in the form of a labeled graph. A universal graph compression scheme is proposed, which does not depend on the underlying statistics/distribution of the graph model. For graphs generated by a stochastic block model, which is a widely used random graph model capturing the clustering effects in social networks, the proposed scheme achieves the optimal theoretical limit of lossless compression without the need to know edge probabilities, community labels, or the number of communities. The key ideas in establishing universality for stochastic block models include: 1) block decomposition of the adjacency matrix of the graph; 2) generalization of the Krichevsky-Trofimov probability assignment, which was initially designed for i.i.d. random processes. In four benchmark graph datasets (protein-to-protein interaction, LiveJournal friendship, Flickr, and YouTube), the compressed files from competing algorithms (including CSR, Ligra+, PNG image compressor, and Lempel-Ziv compressor for two-dimensional data) take 2.4 to 27 times the space needed by the proposed scheme.

When communicating agents form opinions about a set of possible options, agreement and disagreement are both possible outcomes. Depending on the context, either can be desirable or undesirable. We show that for nonlinear opinion dynamics on networks, and a variety of network structures, the spectral properties of the underlying adjacency matrix fully characterize the occurrence of either agreement or disagreement. We further show how the corresponding eigenvector centrality, as well as any symmetry in the network, informs the resulting patterns of opinion formation and agent sensitivity to input that triggers opinion cascades., 6 pages, 4 figures; accepted to appear in 2021 American Control Conference proceedings

Network community detection with higher-order features has become a hot research topic recently since higher-order features that are captured at the level of small network subgraphs can help to gain new insights into the higher-order organizations of the overall network. However, most of the existing higher-order community detection methods only leverage the structural information of networks, yet fail to consider the rich information of node attributes, which typically makes them incapable of discovering semantically meaningful communities. To address this problem, we propose a novel method for community detection based on a newly designed higher-order feature termed Attribute Homogenous Motif (AHMotif), which integrates both node attributes and higher-order structure of the network in a seamless way. Specifically, the statistically significant motifs are identified for the network in terms of the topological structure, and homogeneity values are computed for structural motifs according to the attributes of the nodes that are involved in the motif. Then, the given attributed network can be further represented via a newly designed AHMotif adjacency matrix. The AHMotif adjacency matrix encodes both structures and attribute information and can characterize the network from a higher-order perspective. Afterward, several proximity based methods are utilized to obtain the final community detection results. Extensive experiments on several real-world data sets have shown the superiority of our AHMotif-based method in community detection.

Spectral clustering is one of the most popular clustering approaches and has been applied in Hyperspectral Image (HSI) clustering well. However, most of these methods are not suitable for large scale HSI. In this paper, based on anchor graph and spatial information, we propose a novel method, called fast spectral clustering based on spatial information (FSCS), which could deal with large scale HSI and have better performance in user's accuracy, average accuracy, overall accuracy and so on. Firstly, based on the physical characteristic of HSI, FSCS algorithm combines the spatial information with spectral information, and uses the spatial nearest points to reconstructs the center point and reveal the local spatial structure. As a result, the correlation of pixels is strengthened and the clustering accuracy is improved. Secondly, the new adjacency matrix is constructed based on anchor graph and thus computational complexity is reduced significantly. Finally, in order to avoid tuning the heat-kernel parameter, the parameter-free strategy is adopted in FSCS. Experiments demonstrate the efficiency and effectiveness of the proposed FSCS algorithm.

Consider a two-hop half-duplex relay channel (source–relay–destination) with a Markovian-constrained relay. The capacity of such channel is shown to be equal to the well-known cut-set upper bound. For the case where the relay-to-destination link is noise-free, the optimal state transition probabilities that give rise to the capacity are determined. This result links the relay channel to Shannon’s entropy maximization by introducing a relay adjacency matrix . For the case where both source-to-relay and relay-to-destination links are noisy, lower bounds on the achievable information rates for various constrained sequences are computed. We conjecture that our numerical bounds are tight. The numerically computed capacities and optimized information rates are significantly higher than the rate achieved by the traditional predetermined time-sharing scheme.

Fathoming out quantum state space is a challenging endeavor due to its exponentially growing dimensionality. At the expense of being bound in its expressiveness, the discrete and finite subspace of graph states is easier to investigate via a pictorial framework accompanied with a theoretical toolkit from the stabilizer formalism. Analyzing hand-drawn graphs is a tedious and time-consuming task and imposes limitations to the problem sizes that can be addressed. Similarly, algorithmic studies using adjacency matrices alone lack the benefit of a visual representation of the states. We argue that applying visual analytics to investigate graph states can be advantageous. To this end, we introduce GraphStateVis, a web-based application for the visual analysis of qubit graph states and their stabilizer groups. Our tool facilitates the interactive construction of a graph through multiple components supported by linking and brushing. The user can explore graph-state-specific properties, including the Pauli-weight distribution of its stabilizer operators and noise thresholds for entanglement criteria. We propose a use case in the context of near-term quantum algorithms to illustrate the capabilities of our prototype. We provide access to GraphStateVis as an open-source project and invite the broader quantum computing and engineering communities to take advantage of this tool and further boost its development., published version, only minor changes, 6+1 pages, 6 figures, https://github.com/graphstatevis (Source Code), https://graphstatevis.github.io/app (Deployed Version) This work has been selected as a Best Paper for the 2021 IEEE Quantum Week conference

Pedestrian trajectory prediction is an active research area with recent works undertaken to embed accurate models of pedestrians social interactions and their contextual compliance into dynamic spatial graphs. However, existing works rely on spatial assumptions about the scene and dynamics, which entails a significant challenge to adapt the graph structure in unknown environments for an online system. In addition, there is a lack of assessment approach for the relational modeling impact on prediction performance. To fill this gap, we propose Social Trajectory Recommender-Gated Graph Recurrent Neighborhood Network, (STR-GGRNN), which uses data-driven adaptive online neighborhood recommendation based on the contextual scene features and pedestrian visual cues. The neighborhood recommendation is achieved by online Nonnegative Matrix Factorization (NMF) to construct the graph adjacency matrices for predicting the pedestrians' trajectories. Experiments based on widely-used datasets show that our method outperforms the state-of-the-art. Our best performing model achieves 12 cm ADE and $\sim$15 cm FDE on ETH-UCY dataset. The proposed method takes only 0.49 seconds when sampling a total of 20K future trajectories per frame.

Based on recent results of applying graph signal processing (GSP) to narrowband angle of arrival estimation for uniform linear arrays, we generalise the analysis to the case of arrays with elements placed arbitrarily in three dimensional space. We comment on the selection of the adjacency matrix, analyse how this new approach compares to the multiple signal classification (MUSIC) algorithm, and provide an efficient implementation. We demonstrate that the GSP approach can perform as well as the MUSIC algorithm in terms of accuracy and computational cost. Simulations indicate that the proposed GSP approach avoids the severe performance degradation with which MUSIC is associated at low signal to noise ratios.

Online detection of anomalies is crucial to enhancing the reliability and resiliency of power systems. We propose a novel data-driven online event detection algorithm with synchrophasor data using graph signal processing. In addition to being extremely scalable, our proposed algorithm can accurately capture and leverage the spatio-temporal correlations of the streaming PMU data. This paper also develops a general technique to decouple spatial and temporal correlations in multiple time series. Finally, we develop a unique framework to construct a weighted adjacency matrix and graph Laplacian for product graph. Case studies with real-world, large-scale synchrophasor data demonstrate the scalability and accuracy of our proposed event detection algorithm. Compared to the state-of-the-art benchmark, the proposed method not only achieves higher detection accuracy but also yields higher computational efficiency.

This paper characterizes the difficulty of estimating a network’s eigenvector centrality only from data on the nodes, i.e., with no information about the topology of the network. We model this nodal data as graph signals generated by passing white noise through generic (not necessarily low-pass) graph filters. Leveraging the spectral properties of graph filters, we estimate the eigenvectors of the adjacency matrix of the underlying network. To this end, a simple selection algorithm is proposed, which chooses the correct eigenvector of the signal covariance matrix with minimal assumptions on the underlying graph filter. We then present a theoretical characterization of the asymptotic and non-asymptotic performance of this algorithm, thus providing a sample complexity bound for the centrality estimation and revealing key elements driving this complexity. Finally, we illustrate the developed insights through a set of numerical experiments on different random graph models.

Network based attacks on ecommerce websites can have serious economic consequences. Hence, anomaly detection in dynamic network traffic has become an increasingly important research topic in recent years. This paper proposes a novel dynamic Graph and sparse Autoencoder based Anomaly Detection algorithm named GAAD. In GAAD, the network traffic over contiguous time intervals is first modelled as a series of dynamic bipartite graph increments. One mode projection is performed on each bipartite graph increment and the adjacency matrix derived. Columns of the resultant adjacency matrix are then used to train a sparse autoencoder to reconstruct it. The sum of squared errors between the reconstructed approximation and original adjacency matrix is then calculated. An online learning algorithm is then used to estimate a Gaussian distribution that models the error distribution. Outlier error values are deemed to represent anomalous traffic flows corresponding to possible attacks. In the experiment, a network emulator was used to generate representative ecommerce traffic flows over a time period of 225 minutes with five attacks injected, including SYN scans, host emulation and DDoS attacks. ROC curves were generated to investigate the influence of the autoencoder hyper-parameters. It was found that increasing the number of hidden nodes and their activation level, and increasing sparseness resulted in improved performance. Analysis showed that the sparse autoencoder was unable to encode the highly structured adjacency matrix structures associated with attacks, hence they were detected as anomalies. In contrast, SVD and variants, such as the compact matrix decomposition, were found to accurately encode the attack matrices, hence they went undetected.

Networks are useful representations of many systems with interacting entities, such as social, biological and physical systems. Characterizing the meso-scale organization, i.e. the community structure, is an important problem in network science. Community detection aims to partition the network into sets of nodes that are densely connected internally but sparsely connected to other dense sets of nodes. Current work on community detection mostly focuses on static networks. However, many real world networks are dynamic, i.e. their structure and properties change with time, requiring methods for dynamic community detection. In this paper, we propose a new stochastic block model (SBM) for modeling the evolution of community membership. Unlike existing SBMs, the proposed model allows each community to evolve at a different rate. This new model is used to derive a maximum a posteriori estimator for community detection, which can be written as a constrained spectral clustering problem. In particular, the transition probabilities for each community modify the graph adjacency matrix at each time point. This formulation provides a relationship between statistical network inference and spectral clustering for dynamic networks. The proposed method is evaluated on both simulated and real dynamic networks.

International audience; In graph signal processing, there are often settings where the graph topology is not known beforehand and has to be estimated from data. Moreover, some graphs can be dynamic, such as brain activity supported by neurons or brain regions. This paper focuses on estimating in an online and adaptive manner a network structure capturing the non-linear dependencies among streaming graph signals in the form of a possibly directed, adjacency matrix. By projecting data into a higher-or infinite-dimension space, we focus on capturing nonlinear relationships between agents. In order to mitigate the increasing number of data points, we employ kernel dictionaries. Finally, we run a series of tests in order to experimentally illustrate the usefulness of our kernel-based approach on biomedical data, on which we obtain results comparable to state-of-the-art methods.

We study the blind centrality ranking problem, where our goal is to infer the eigenvector centrality ranking of nodes solely from nodal observations, i.e., without information about the topology of the network. We formalize these nodal observations as graph signals and model them as the outputs of a network process on the underlying (unobserved) network. A simple spectral algorithm is proposed to estimate the leading eigenvector of the associated adjacency matrix, thus serving as a proxy for the centrality ranking. A finite rate performance analysis of the algorithm is provided, where we find a lower bound on the number of graph signals needed to correctly rank (with high probability) two nodes of interest. We then specialize our general analysis for the particular case of dense Erdős-Renyi graphs, where existing graph-theoretical results can be leveraged. Finally, we illustrate the proposed algorithm via numerical experiments on synthetic and real-world networks, with special emphasis on how the network features influence the performance.

A Bicycle-sharing system (BSS) is a popular service scheme deployed in cities of different sizes around the world. Efficiently keeping bicycle-sharing system as balanced as possible is the main problem and thus, predicting or minimizing the manual transportation of bikes across the city is the prime objective in order to save logistic costs for operating companies. The purpose of this paper is two-fold: Identification of spatial structures and their structural change using Convolutional neural network (CNN) that takes adjacency matrix snapshots of unbalanced sub-graphs, and the Long short-term memory artificial recurrent neural network (RNN LSTM) in order to find and predict its dynamic patterns. As a result, we are predicting bike flows for each node in the possible future subgraph configuration, which in turn informs bicycle-sharing system owners to plan accordingly. Benefits are identified both for urban city planning and for bike-sharing companies by saving time and minimizing their cost.

We consider the Nash equilibrium problem in a partial-decision information scenario. Specifically, each agent can only receive information from some neighbors via a communication network, while its cost function depends on the strategies of possibly all agents. In particular, while the existing methods assume undirected or balanced communication, in this paper we allow for non-balanced, directed graphs. We propose a fully-distributed pseudo-gradient scheme, which is guaranteed to converge with linear rate to a Nash equilibrium, under strong monotonicity and Lipschitz continuity of the game mapping. Our algorithm requires global knowledge of the communication structure, namely of the Perron-Frobenius eigenvector of the adjacency matrix and of a certain constant related to the graph connectivity. Therefore, we adapt the procedure to setups where the network is not known in advance, by computing the eigenvector online and by means of vanishing step sizes., To appear in the 59th Conference on Decision and Control (CDC 2020)

Reliable information processing is a hallmark of many physical and biological networked systems. In this paper, we propose a novel framework for modelling information transmission within a linear dynamical network. Information propagation is modelled by means of a digital communication protocol that takes into account the realistic phenomenon of inter-symbol interference. Building on this framework, we adopt Shannon information rate to quantify the amount of information that can be reliably sent over the network within a fixed time window. We investigate how the latter information metric is affected by the connectivity structure of the network. Here, we focus in particular on networks characterized by a normal adjacency matrix. We show that for such networks the maximum achievable information rate depends only on the spectrum of the adjacency matrix. We then provide numerical results suggesting that non-normal network architectures could benefit information transmission in our framework.

Dense heterogeneous network serves as one of the most promising technologies for the upcoming 5G network. However, with a larger number of densely deployed small cells, the problem of co-channel interference and power consumption of 5G small cell base stations (also known as S-gNBs) becomes more severe. In order to improve the power efficiency and alleviate the co-channel interference, S-gNBs in the network need to be dynamically switched on or off via appropriate criteria or strategies. This paper proposes an interference contribution rate (ICR) based small cell on/off switching algorithm. With the incorporation of network adjacency matrix (NAM), the proposed algorithm circumvents the complicated computation of the ICRs of the S-gNBs in the network and hence yields less computational complexity. In addition, the proposed algorithm identifies the S-gNBs that need to be switched on or off based on the NAM and the serving signal strength measurements of user equipment’s and therefore involves less signaling information in the procedure of switching on/off decision. Simulation results verify that the proposed algorithm effectively diminishes the co-channel interference among the small cells, ameliorates the network power efficiency and total data rate, and meanwhile maintains a lower traffic loss in the network.

The length of an optimal scalar linear index code of a groupcast index coding problem is equal to the minrank of its side-information hypergraph. The side-information hyper-graph becomes a side-information graph for a special class of groupcast index coding problems known as unicast index coding problems. The number of computations required to find the minrank of a side-information graph depends on the number of edges present in the side-information graph. In this paper, we define the notion of minrank-critical edges in a side-information graph and derive some properties of minrank, which identifies minrank-non-critical edges. Using these properties we present a method to reduce the number of computations required to compute minrank. Apart from this, we give a heuristic method to compute minrank. Also, we give an heuristic algorithm to find a clique cover of the side-information graph by using some binary operations on the adjacency matrix of the side-information graph. We also give a method to convert a groupcast index coding problem into a single unicast index coding problem. Combining all these results, we give a method to construct index codes (with not necessarily optimal length) for groupcast index coding problems. The construction technique is independent of field size and hence can be used to construct index codes over the binary field. In some cases the constructed index codes are better than the best known in the literature both in terms of the length of the code and the minimum field size required.