liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Methods and algorithms for control input placement in complex networks
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-4049-6018
2018 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

The control-theoretic notion of controllability captures the ability to guide a systems behavior toward a desired state with a suitable choice of inputs. Controllability of complex networks such as traffic networks, gene regulatory networks, power grids etc. brings many opportunities. It could for instance enable improved efficiency in the functioning of a network or lead to that entirely new applicative possibilities emerge. However, when control theory is applied to complex networks like these, several challenges arise. This thesis consider some of these challenges, in particular we investigate how control inputs should be placed in order to render a given network controllable at a minimum cost, taking as cost function either the number of control inputs or the energy that they must exert. We assume that each control input targets only one node (called a driver node) and is either unconstrained or unilateral.

A unilateral control input is one that can assume either positive or negative values but not both. Motivated by the many applications where unilateral controls are common, we reformulate classical controllability results for this particular case into a more computationally-efficient form that enables a large scale analysis. We show that the unilateral controllability problem is to a high degree structural and derive theoretical lower bounds on the minimal number of unilateral control inputs from topological properties of the network, similar to the bounds that exists for the minimal number of unconstrained control inputs. Moreover, an algorithm is developed that constructs a near minimal number of control inputs for a given network. When evaluated on various categories of random networks as well as a number of real-world networks, the algorithm often achieves the theoretical lower bounds.

A network can be controllable in theory but not in practice when completely unreasonable amounts of control energy are required to steer it in some direction. For unconstrained control inputs we show that the control energy depends on the time constants of the modes of the network, and that the closer the eigenvalues are to the imaginary axis of the complex plane, the less energy is required for control. We also investigate the problem of placing driver nodes such that the control energy requirements are minimized (assuming that theoretical controllability is not an issue). For the special case with networks having all purely imaginary eigenvalues, several constructive algorithms for driver node placement are developed. In order to understand what determines the control energy in the general case with arbitrary eigenvalues, we define two centrality measures for the nodes based on energy flow considerations: the first centrality reflects the network impact of a node and the second the ability to control it indirectly. It turns out that whether a node is suitable as driver node or not largely depends on these two qualities. By combining the centralities into node rankings we obtain driver node placements that significantly reduce the control energy requirements and thereby improve the “practical degree of controllability”.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2018. , p. 36
Series
Linköping Studies in Science and Technology. Licentiate Thesis, ISSN 0280-7971 ; 1814
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:liu:diva-150886DOI: 10.3384/lic.diva-150886ISBN: 9789176852439 (print)OAI: oai:DiVA.org:liu-150886DiVA, id: diva2:1244823
Presentation
2018-08-30, 00:00 (English)
Opponent
Supervisors
Note

Minor corrections are made in the electronic version of the thesis (Abstract). / Mindre korreigeringar är gjorda i den elektroniska versionen av avhandlingen (i Abstract).

Available from: 2018-09-03 Created: 2018-09-03 Last updated: 2019-10-12Bibliographically approved
List of papers
1. Controllability of complex networks with unilateral inputs
Open this publication in new window or tab >>Controllability of complex networks with unilateral inputs
2017 (English)In: Scientific Reports, ISSN 2045-2322, E-ISSN 2045-2322, Vol. 7, article id 1824Article in journal (Refereed) Published
Abstract [en]

In this paper, we study the problem of controlling complex networks with unilateral controls, i.e., controls which can assume only positive or negative values, not both. Given a complex network represented by the adjacency matrix A, an algorithm is developed that constructs an input matrix B such that the resulting system (A, B) is controllable with a near minimal number of unilateral control inputs. This is made possible by a reformulation of classical conditions for controllability that casts the minimal unilateral input selection problem into well known optimization problems. We identify network properties that make unilateral controllability relatively easy to achieve as compared to unrestricted controllability. The analysis of the network topology for instance allows us to establish theoretical bounds on the minimal number of controls required. For various categories of random networks as well as for a number of real-world networks these lower bounds are often achieved by our heuristics.

Place, publisher, year, edition, pages
NATURE PUBLISHING GROUP, 2017
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-138253 (URN)10.1038/s41598-017-01846-6 (DOI)000401262400017 ()28500342 (PubMedID)
Available from: 2017-06-13 Created: 2017-06-13 Last updated: 2019-07-05
2. Minimum energy control for complex networks
Open this publication in new window or tab >>Minimum energy control for complex networks
2018 (English)In: Scientific Reports, ISSN 2045-2322, E-ISSN 2045-2322, Vol. 8, article id 3188Article in journal (Refereed) Published
Abstract [en]

The aim of this paper is to shed light on the problem of controlling a complex network with minimal control energy. We show first that the control energy depends on the time constant of the modes of the network, and that the closer the eigenvalues are to the imaginary axis of the complex plane, the less energy is required for complete controllability. In the limit case of networks having all purely imaginary eigenvalues (e.g. networks of coupled harmonic oscillators), several constructive algorithms for minimum control energy driver node selection are developed. A general heuristic principle valid for any directed network is also proposed: the overall cost of controlling a network is reduced when the controls are concentrated on the nodes with highest ratio of weighted outdegree vs indegree.

Place, publisher, year, edition, pages
NATURE PUBLISHING GROUP, 2018
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:liu:diva-145766 (URN)10.1038/s41598-018-21398-7 (DOI)000425285200018 ()29453421 (PubMedID)
Note

Funding Agencies|Swedish Research Council [2015-04390]

Available from: 2018-03-22 Created: 2018-03-22 Last updated: 2019-07-05

Open Access in DiVA

Methods and algorithms for control input placement in complex networks(1663 kB)201 downloads
File information
File name FULLTEXT02.pdfFile size 1663 kBChecksum SHA-512
906eb140cf18696a62082b23194f361aaa2a63279b74cff27d61bc304d19b0d5483bb9573464d3045e7c81065e0e5f48ef078a03a66369e1be5fe9d6670f5142
Type fulltextMimetype application/pdf
omslag(33 kB)11 downloads
File information
File name COVER01.pdfFile size 33 kBChecksum SHA-512
0720d36bb5f255b86f4142daefa4179c3348de0410ec42fb8103ebad31b0c97482130adcde5e8d094fc7c89c69d7cb82ff1569f7037513b9406fa8b92b4dabe2
Type coverMimetype application/pdf
Order online >>

Other links

Publisher's full text

Authority records BETA

Lindmark, Gustav

Search in DiVA

By author/editor
Lindmark, Gustav
By organisation
Automatic ControlFaculty of Science & Engineering
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 212 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 369 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf