Loading…
Minimal Edge Addition for Network Controllability
We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of dire...
Saved in:
| Published in: | IEEE transactions on control of network systems 2019-03, Vol.6 (1), p.312-323 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433 |
| container_end_page | 323 |
| container_issue | 1 |
| container_start_page | 312 |
| container_title | IEEE transactions on control of network systems |
| container_volume | 6 |
| creator | Chen, Ximing Pequito, Sergio Pappas, George J. Preciado, Victor M. |
| description | We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of directed edges that need to be added to the network topology in order to render a structurally controllable system. Our main contribution is twofold: first, we provide a full characterization of all optimal network modifications, and second, we propose an algorithm able to find an optimal solution in polynomial time. We illustrate the validity of our algorithm via numerical simulations in random networked systems. |
| doi_str_mv | 10.1109/TCNS.2018.2814841 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_ieee_</sourceid><recordid>TN_cdi_ieee_primary_8310926</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>8310926</ieee_id><sourcerecordid>2194173194</sourcerecordid><originalsourceid>FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433</originalsourceid><addsrcrecordid>eNpNkN9LwzAQgIMoOOb-APGl4HPn3SVp2sdRphPmfHA-h3RNpLM2M-2Q_fdmbIgv9wO-u-M-xm4RpohQPKzL1duUAPMp5ShygRdsRJxkKnMFl__qazbp-y0AIMnY8xHDl6ZrvkybzOsPm8zquhka3yXOh2Rlhx8fPpPSd0PwbWuqpm2Gww27cqbt7eScx-z9cb4uF-ny9em5nC3TjQAaUmuQcyApjKmcqhRIKbgrQGXGABpn0dRkBVWKk6tyUJSJgmQmMyQgwfmY3Z_27oL_3tt-0Fu_D108qQkLgYrHGCk8UZvg-z5Yp3ch_hMOGkEf5eijHH2Uo89y4szdaaax1v7xOY80ZfwX2ZRdcw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2194173194</pqid></control><display><type>article</type><title>Minimal Edge Addition for Network Controllability</title><source>IEEE Electronic Library (IEL) Journals</source><creator>Chen, Ximing ; Pequito, Sergio ; Pappas, George J. ; Preciado, Victor M.</creator><creatorcontrib>Chen, Ximing ; Pequito, Sergio ; Pappas, George J. ; Preciado, Victor M.</creatorcontrib><description>We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of directed edges that need to be added to the network topology in order to render a structurally controllable system. Our main contribution is twofold: first, we provide a full characterization of all optimal network modifications, and second, we propose an algorithm able to find an optimal solution in polynomial time. We illustrate the validity of our algorithm via numerical simulations in random networked systems.</description><identifier>ISSN: 2325-5870</identifier><identifier>EISSN: 2325-5870</identifier><identifier>EISSN: 2372-2533</identifier><identifier>DOI: 10.1109/TCNS.2018.2814841</identifier><identifier>CODEN: ITCNAY</identifier><language>eng</language><publisher>Piscataway: IEEE</publisher><subject>Algorithm design and analysis ; Algorithms ; Bipartite graph ; Computer simulation ; Controllability ; Heuristic algorithms ; Network topologies ; Network topology ; Optimization ; Polynomials ; Topology</subject><ispartof>IEEE transactions on control of network systems, 2019-03, Vol.6 (1), p.312-323</ispartof><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) 2019</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433</citedby><cites>FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433</cites><orcidid>0000-0001-9081-0637 ; 0000-0001-8670-8031 ; 0000-0002-5143-1543 ; 0000-0001-9998-8730</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/8310926$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,54796</link.rule.ids></links><search><creatorcontrib>Chen, Ximing</creatorcontrib><creatorcontrib>Pequito, Sergio</creatorcontrib><creatorcontrib>Pappas, George J.</creatorcontrib><creatorcontrib>Preciado, Victor M.</creatorcontrib><title>Minimal Edge Addition for Network Controllability</title><title>IEEE transactions on control of network systems</title><addtitle>TCNS</addtitle><description>We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of directed edges that need to be added to the network topology in order to render a structurally controllable system. Our main contribution is twofold: first, we provide a full characterization of all optimal network modifications, and second, we propose an algorithm able to find an optimal solution in polynomial time. We illustrate the validity of our algorithm via numerical simulations in random networked systems.</description><subject>Algorithm design and analysis</subject><subject>Algorithms</subject><subject>Bipartite graph</subject><subject>Computer simulation</subject><subject>Controllability</subject><subject>Heuristic algorithms</subject><subject>Network topologies</subject><subject>Network topology</subject><subject>Optimization</subject><subject>Polynomials</subject><subject>Topology</subject><issn>2325-5870</issn><issn>2325-5870</issn><issn>2372-2533</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2019</creationdate><recordtype>article</recordtype><recordid>eNpNkN9LwzAQgIMoOOb-APGl4HPn3SVp2sdRphPmfHA-h3RNpLM2M-2Q_fdmbIgv9wO-u-M-xm4RpohQPKzL1duUAPMp5ShygRdsRJxkKnMFl__qazbp-y0AIMnY8xHDl6ZrvkybzOsPm8zquhka3yXOh2Rlhx8fPpPSd0PwbWuqpm2Gww27cqbt7eScx-z9cb4uF-ny9em5nC3TjQAaUmuQcyApjKmcqhRIKbgrQGXGABpn0dRkBVWKk6tyUJSJgmQmMyQgwfmY3Z_27oL_3tt-0Fu_D108qQkLgYrHGCk8UZvg-z5Yp3ch_hMOGkEf5eijHH2Uo89y4szdaaax1v7xOY80ZfwX2ZRdcw</recordid><startdate>20190301</startdate><enddate>20190301</enddate><creator>Chen, Ximing</creator><creator>Pequito, Sergio</creator><creator>Pappas, George J.</creator><creator>Preciado, Victor M.</creator><general>IEEE</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0001-9081-0637</orcidid><orcidid>https://orcid.org/0000-0001-8670-8031</orcidid><orcidid>https://orcid.org/0000-0002-5143-1543</orcidid><orcidid>https://orcid.org/0000-0001-9998-8730</orcidid></search><sort><creationdate>20190301</creationdate><title>Minimal Edge Addition for Network Controllability</title><author>Chen, Ximing ; Pequito, Sergio ; Pappas, George J. ; Preciado, Victor M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2019</creationdate><topic>Algorithm design and analysis</topic><topic>Algorithms</topic><topic>Bipartite graph</topic><topic>Computer simulation</topic><topic>Controllability</topic><topic>Heuristic algorithms</topic><topic>Network topologies</topic><topic>Network topology</topic><topic>Optimization</topic><topic>Polynomials</topic><topic>Topology</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Chen, Ximing</creatorcontrib><creatorcontrib>Pequito, Sergio</creatorcontrib><creatorcontrib>Pappas, George J.</creatorcontrib><creatorcontrib>Preciado, Victor M.</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE Electronic Library (IEL)【Remote access available】</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on control of network systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Chen, Ximing</au><au>Pequito, Sergio</au><au>Pappas, George J.</au><au>Preciado, Victor M.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Minimal Edge Addition for Network Controllability</atitle><jtitle>IEEE transactions on control of network systems</jtitle><stitle>TCNS</stitle><date>2019-03-01</date><risdate>2019</risdate><volume>6</volume><issue>1</issue><spage>312</spage><epage>323</epage><pages>312-323</pages><issn>2325-5870</issn><eissn>2325-5870</eissn><eissn>2372-2533</eissn><coden>ITCNAY</coden><abstract>We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of directed edges that need to be added to the network topology in order to render a structurally controllable system. Our main contribution is twofold: first, we provide a full characterization of all optimal network modifications, and second, we propose an algorithm able to find an optimal solution in polynomial time. We illustrate the validity of our algorithm via numerical simulations in random networked systems.</abstract><cop>Piscataway</cop><pub>IEEE</pub><doi>10.1109/TCNS.2018.2814841</doi><tpages>12</tpages><orcidid>https://orcid.org/0000-0001-9081-0637</orcidid><orcidid>https://orcid.org/0000-0001-8670-8031</orcidid><orcidid>https://orcid.org/0000-0002-5143-1543</orcidid><orcidid>https://orcid.org/0000-0001-9998-8730</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 2325-5870 |
| ispartof | IEEE transactions on control of network systems, 2019-03, Vol.6 (1), p.312-323 |
| issn | 2325-5870 2325-5870 2372-2533 |
| language | eng |
| recordid | cdi_ieee_primary_8310926 |
| source | IEEE Electronic Library (IEL) Journals |
| subjects | Algorithm design and analysis Algorithms Bipartite graph Computer simulation Controllability Heuristic algorithms Network topologies Network topology Optimization Polynomials Topology |
| title | Minimal Edge Addition for Network Controllability |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-05T21%3A34%3A55IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_ieee_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Minimal%20Edge%20Addition%20for%20Network%20Controllability&rft.jtitle=IEEE%20transactions%20on%20control%20of%20network%20systems&rft.au=Chen,%20Ximing&rft.date=2019-03-01&rft.volume=6&rft.issue=1&rft.spage=312&rft.epage=323&rft.pages=312-323&rft.issn=2325-5870&rft.eissn=2325-5870&rft.coden=ITCNAY&rft_id=info:doi/10.1109/TCNS.2018.2814841&rft_dat=%3Cproquest_ieee_%3E2194173194%3C/proquest_ieee_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c402t-ea1330254aabf7b705543f9076aa01afe1ad2e42b732fb8072649256561202433%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2194173194&rft_id=info:pmid/&rft_ieee_id=8310926&rfr_iscdi=true |