skip to main content

Explore Research Products in the NSF-PAR

Title: Selecting energy efficient inputs using graph structure
Selecting appropriate inputs for systems described by complex networks is an important but difficult problem that largely remains open in the field of control of networks. Recent work has proposed two methods for energy efficient input selection; a gradient-based heuristic and a greedy approximation algorithm. We propose here an alternative method for input selection based on the analytic solution of the controllability Gramian of the ‘balloon graph’, a special model graph that captures the role of both distance and redundant paths between a driver node and a target node. The method presented is especially applicable for large networks where one is interested in controlling only a small number of outputs, or target nodes, for which current methods may not be practical because they require computing a typically very ill-conditioned matrix, called the controllability Gramian. Our method produces comparable results to the previous methods while being more computational efficient.  more » « less
Award ID(s):
1727948
NSF-PAR ID:
10319883
Author(s) / Creator(s):
;
Date Published:
Journal Name:
International Journal of Control
Volume:
1
Issue:
1
ISSN:
0020-7179
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , Scientific Reports)
    null (Ed.)
    Abstract Recent advances in network science, control theory, and fractional calculus provide us with mathematical tools necessary for modeling and controlling complex dynamical networks (CDNs) that exhibit long-term memory. Selecting the minimum number of driven nodes such that the network is steered to a prescribed state is a key problem to guarantee that complex networks have a desirable behavior. Therefore, in this paper, we study the effects of long-term memory and of the topological properties on the minimum number of driven nodes and the required control energy. To this end, we introduce Gramian-based methods for optimal driven node selection for complex dynamical networks with long-term memory and by leveraging the structure of the cost function, we design a greedy algorithm to obtain near-optimal approximations in a computationally efficiently manner. We investigate how the memory and topological properties influence the control effort by considering Erdős–Rényi, Barabási–Albert and Watts–Strogatz networks whose temporal dynamics follow a fractional order state equation. We provide evidence that scale-free and small-world networks are easier to control in terms of both the number of required actuators and the average control energy. Additionally, we show how our method could be applied to control complex networks originating from the human brain and we discover that certain brain cortex regions have a stronger impact on the controllability of network than others. 
    more » « less
  2. ; ( , 2022 American Control Conference (ACC))
    In this paper, we consider the problem of sensor selection for discrete-time linear dynamical networks. We develop a framework to design a sparse sensor schedule for a given large-scale linear system with guaranteed performance bounds using a learning-based algorithm. To sparsify the sensors in both time and space, we build our combinatorial optimization problems based on the notion of systemic controllability/observability metrics for linear dynamical networks with three properties: monotonicity, convexity, and homogeneity with respect to the controllability/observability Gramian matrix of the network. These combinatorial optimizations are inherently intractable and NP-hard. However, solving a continuous relaxation for each optimization is considered best practice. This is achievable since we constructed the objective based on the systemic metrics, which are convex. Furthermore, by leveraging recent advances in sparsification literature and regret minimization, we then round the fractional solution obtained by the continuous optimization to achieve a (1+epsilon) approximation sparse schedule that chooses on average a constant number of sensors at each time, to approximate all types of systemic metrics. 
    more » « less
  3. ; ; ; ( , Proceedings of the VLDB Endowment)
    n recent years, we have seen the success of network representation learning (NRL) methods in diverse domains ranging from com- putational chemistry to drug discovery and from social network analysis to bioinformatics algorithms. However, each such NRL method is typically prototyped in a programming environment familiar to the developer. Moreover, such methods rarely scale out to large-scale networks or graphs. Such restrictions are problematic to domain scientists or end-users who want to scale a particular NRL method-of-interest on large graphs from their specific domain. In this work, we present a novel system, WebMILE to democ- ratize this process. WebMILE can scale an unsupervised network embedding method written in the user’s preferred programming language on large graphs. It provides an easy-to-use Graphical User Interface (GUI) for the end-user. The user provides the necessary in- put (embedding method file, graph, required packages information) through a simple GUI, and WebMILE executes the input network embedding method on the given input graph. WebMILE leverages a pioneering multi-level method, MILE (alternatively DistMILE if the user has access to a cluster), that can scale a network embed- ding method on large graphs. The language agnosticity is achieved through a simple Docker interface. In this demonstration, we will showcase how a domain scientist or end-user can utilize WebMILE to rapidly prototype and learn node embeddings of a large graph in a flexible and efficient manner - ensuring the twin goals of high productivity and high performance. 
    more » « less
  4. ; ; ; ; ; ; ( , Proceedings of the 28th International Conference on Computational Linguistics)
    null (Ed.)
    Network representation learning (NRL) is crucial in the area of graph learning. Recently, graph autoencoders and its variants have gained much attention and popularity among various types of node embedding approaches. Most existing graph autoencoder-based methods aim to minimize the reconstruction errors of the input network while not explicitly considering the semantic relatedness between nodes. In this paper, we propose a novel network embedding method which models the consistency across different views of networks. More specifically, we create a second view from the input network which captures the relation between nodes based on node content and enforce the latent representations from the two views to be consistent by incorporating a multiview adversarial regularization module. The experimental studies on benchmark datasets prove the effectiveness of this method, and demonstrate that our method compares favorably with the state-of-the-art algorithms on challenging tasks such as link prediction and node clustering. We also evaluate our method on a real-world application, i.e., 30-day unplanned ICU readmission prediction, and achieve promising results compared with several baseline methods. 
    more » « less
  5. ; ; ; ; ( , BigData)
    Network alignment is a fundamental task in many high-impact applications. Most of the existing approaches either explicitly or implicitly consider the alignment matrix as a linear transformation to map one network to another, and might overlook the complicated alignment relationship across networks. On the other hand, node representation learning based alignment methods are hampered by the incomparability among the node representations of different networks. In this paper, we propose a unified semi-supervised deep model (ORIGIN) that simultaneously finds the non-rigid network alignment and learns node representations in multiple networks in a mutually beneficial way. The key idea is to learn node representations by the effective graph convolutional networks, which subsequently enable us to formulate network alignment as a point set alignment problem. The proposed method offers two distinctive advantages. First (node representations), unlike the existing graph convolutional networks that aggregate the node information within a single network, we can effectively aggregate the auxiliary information from multiple sources, achieving far-reaching node representations. Second (network alignment), guided by the highquality node representations, our proposed non-rigid point set alignment approach overcomes the bottleneck of the linear transformation assumption. We conduct extensive experiments that demonstrate the proposed non-rigid alignment method is (1) effective, outperforming both the state-of-the-art linear transformation-based methods and node representation based methods, and (2) efficient, with a comparable computational time between the proposed multi-network representation learning component and its single-network counterpart. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email