This paper provides a framework to evaluate the performance of single and double integrator networks over arbitrary directed graphs. Adopting vehicular network terminology, we consider quadratic performance metrics defined by the L2-norm of position and velocity based response functions given impulsive inputs to each vehicle. We exploit the spectral properties of weighted graph Laplacians and output performance matrices to derive a novel method of computing the closed-form solutions for this general class of performance metrics, which include H2-norm based quantities as special cases. We then explore the effect of the interplay between network properties (such as edge directionality and connectivity) and the control strategy on the overall network performance. More precisely, for systems whose interconnection is described by graphs with normal Laplacian L, we characterize the role of directionality by comparing their performance with that of their undirected counterparts, represented by the Hermitian part of L. We show that, for single-integrator networks, directed and undirected graphs perform identically. However, for double-integrator networks, graph directionality -expressed by the eigenvalues of L with nonzero imaginary part- can significantly degrade performance. Interestingly, in many cases, well-designed feedback can also exploit directionality to mitigate degradation or even improve the performance to exceed that of the undirected case. Finally we focus on a system coherence metric -aggregate deviation from the state average- to investigate the relationship between performance and degree of connectivity, leading to somewhat surprising findings. For example, increasing the number of neighbors on a ω-nearest neighbor directed graph does not necessarily improve performance. Similarly, we demonstrate equivalence in performance between all-to-one and all-to-all communication graphs.
more »
« less
Detecting Aberrant Linking Behavior in Directed Networks [Detecting Aberrant Linking Behavior in Directed Networks]
Agents with aberrant behavior are commonplace in today’s networks. There are fake profiles in social media, malicious websites on the internet, and fake news sources that are prolific in spreading misinformation. The distinguishing characteristic of networks with aberrant agents is that normal agents rarely link to aberrant ones. Based on this manifested behavior, we propose a directed Markov Random Field (MRF) formulation for detecting aberrant agents. The formulation balances two objectives: to have as few links as possible
from normal to aberrant agents, as well as to deviate minimally from prior information (if given). The MRF formulation is solved optimally and efficiently. We compare the optimal solution for the MRF formulation to
existing algorithms, including PageRank, TrustRank, and AntiTrustRank. To assess the performance of these algorithms, we present a variant of the modularity clustering metric that overcomes the known shortcomings of
modularity in directed graphs. We show that this new metric has desirable properties and prove that optimizing it is NP-hard. In an empirical experiment with twenty-three different datasets, we demonstrate that the MRF
method outperforms the other detection algorithms.
more »
« less
- Award ID(s):
- 1760102
- NSF-PAR ID:
- 10357234
- Date Published:
- Journal Name:
- Proceedings of the 11th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management
- Volume:
- IC3K 2019
- Page Range / eLocation ID:
- 72 to 82
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract The multilayer network framework has served to describe and uncover a number of novel and unforeseen physical behaviors and regimes in interacting complex systems. However, the majority of existing studies are built on undirected multilayer networks while most complex systems in nature exhibit directed interactions. Here, we propose a framework to analyze diffusive dynamics on multilayer networks consisting of at least one directed layer. We rigorously demonstrate that directionality in multilayer networks can fundamentally change the behavior of diffusive dynamics: from monotonic (in undirected systems) to non-monotonic diffusion with respect to the interlayer coupling strength. Moreover, for certain multilayer network configurations, the directionality can induce a unique superdiffusion regime for intermediate values of the interlayer coupling, wherein the diffusion is even faster than that corresponding to the theoretical limit for undirected systems, i.e. the diffusion in the integrated network obtained from the aggregation of each layer. We theoretically and numerically show that the existence of superdiffusion is fully determined by the directionality of each layer and the topological overlap between layers. We further provide a formulation of multilayer networks displaying superdiffusion. Our results highlight the significance of incorporating the interacting directionality in multilevel networked systems and provide a framework to analyze dynamical processes on interconnected complex systems with directionality.
-
more » « less
Abstract The quality of network clustering is often measured in terms of a commonly used metric known as “modularity”. Modularity compares the clusters found in a network to those present in a random graph (a “null model”). Unfortunately, modularity is somewhat ill suited for studying spatially embedded networks, since a random graph contains no basic geometrical notions. Regardless of their distance, the null model assigns a nonzero probability for an edge to appear between any pair of nodes. Here, we propose a variant of modularity that does not rely on the use of a null model. To demonstrate the essentials of our method, we analyze networks generated from granular ensemble. We show that our method performs better than the most commonly used Newman-Girvan (NG) modularity in detecting the best (physically transparent) partitions in those systems. Our measure further properly detects hierarchical structures, whenever these are present.
-
more » « less
Red blood cell (RBC) disorders such as sickle cell disease affect billions worldwide. While much attention focuses on altered properties of aberrant RBCs and corresponding hemodynamic changes, RBC disorders are also associated with vascular dysfunction, whose origin remains unclear and which provoke severe consequences including stroke. Little research has explored whether biophysical alterations of RBCs affect vascular function. We use a detailed computational model of blood that enables characterization of cell distributions and vascular stresses in blood disorders and compare simulation results with experimental observations. Aberrant RBCs, with their smaller size and higher stiffness, concentrate near vessel walls (marginate) because of contrasts in physical properties relative to normal cells. In a curved channel exemplifying the geometric complexity of the microcirculation, these cells distribute heterogeneously, indicating the importance of geometry. Marginated cells generate large transient stress fluctuations on vessel walls, indicating a mechanism for the observed vascular inflammation.
-
ZigBee is a popular wireless communication standard for Internet of Things (IoT) networks. Since each ZigBee network uses hop-by-hop network-layer message authentication based Yanchao Zhang Arizona State University Star E E Tree E E R E Mesh E E R E E E on a common network key, it is highly vulnerable to packetC E injection attacks, in which the adversary exploits the compromised network key to inject arbitrary fake packets from any spoofed address to disrupt network operations and conCoordinator C R E sume the network/device resources. In this paper, we present PhyAuth, a PHY hop-by-hop message authentication frameE E C R R E E E R R C R E E Router E E E End Device Figure 1: ZigBee network topologies. work to defend against packet-injection attacks in ZigBee networks. The key idea of PhyAuth is to let each ZigBee E The coordinator acts as a central node responsible for mantransmitter embed into its PHY signals a PHY one-time password (called POTP) derived from a device-specific secret key and an efficient cryptographic hash function. An authentic POTP serves as the transmitter’s PHY transmission permission for the corresponding packet. PhyAuth provides three schemes to embed, detect, and verify POTPs based on different features of ZigBee PHY signals. In addition, PhyAuth involves lightweight PHY signal processing and no change to the ZigBee protocolstack. Comprehensive USRP experiments confirm that PhyAuth can efficiently detect fake packets with very low false-positive and false-negative rates while having a negligible negative impact on normal data transmissions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.5220/0008069600720082
