Topological Clusters in Consensus Networks : Analysis and Design

Abstract

This dissertation investigates the clustering phenomena in directed consensus networks and develops a systematic framework for analyzing and designing such networks from a topological perspective. The main objective is to reveal how the structural connectivity of a directed graph determines the steady-state behavior of collectively interacting agents, independent of the edge weights. First, the study introduces the concept of topological clusters (TCs), defined as maximal subsets of nodes that converge to identical steady-state values solely as a result of the network topology. Unlike conventional cluster consensus, which depends on edge weights or initial conditions, the notion of TCs captures the structural influence of topology on asymptotic behavior. A necessary and sufficient condition for a subset of nodes to become a topological cluster has been derived, and it provides a rigorous theoretical basis for understanding how topological connectivity governs clustering. This theoretical insight serves as the foundation for algorithms that identify and classify topological clusters using structural information alone. Building on this theoretical foundation, this dissertation addresses the design of a network that realizes targeted topological clusters (TTCs) as topological clusters. To achieve this goal, three edge modification schemes are proposed. The first establishes directed spanning trees within each TTC to ensure internal connectivity. The second scheme removes invalid incoming edges so that the internal agreement of each TTC is maintained. The third scheme enforces the maximality that guarantees the uniqueness of the realized topological clusters. Each scheme is associated with a corresponding design cost that quantifies the minimal number of edge additions and removals required. By minimizing the total design cost, the optimal pseudo-CR nodes are determined, which serve as structural anchors in the design procedure. The proposed algorithms enable the realization of both leader and follower TTCs with minimal structural modification and provide an effective approach to designing consensus networks that exhibit designated clustering behavior.|본 학위논문은 유방향 합의 네트워크에서 나타나는 클러스터링 현상을 위상적 관점에서 분석하고,이러한네트워크의구조를설계하기위한통합적인프레임워크를제안한다.본연구의 목적은 그래프의 구조적 연결성이 서로 상호작용하는 노드들의 정상 상태 수렴 경향을 어떻게 결정하는지를규명하는데있다. 먼저, 네트워크의 토폴로지에 의해서만 동일한 정상 상태로 수렴하는 노드들의 최대 집합을 위상적클러스터로정의한다.간선가중치나초기상태에의존하는기존의클러스터와는달리,위 상적클러스터개념은그래프의구조가수렴경향에미치는순수한위상적영향에집중한다.또한, 어떤노드집합이위상적클러스터가되기위한필요충분조건을제시하였으며,이를통해위상적 연결성이클러스터링현상을결정하는원리를엄밀히규명하였다.이이론적결과는그래프의구 조적정보만을이용하여클러스터를체계적으로식별하고분류할수있는알고리즘개발의기반이 된다. 이러한 이론적 토대를 바탕으로, 본 논문은 주어진 네트워크가 설계 목표로 설정된 가상의 클 러스터를 실제 위상적 클러스터로 실현하도록 하는 역설계 문제를 다룬다. 이를 위해 세 가지로 구성된 간선 수정 방법을 제안하였다. 첫 번째 방법은 주어진 가상의 클러스터 내부에 속한 노드 들로유방향스패닝트리를구성하여내부연결성을확보한다.두번째방법은외부로부터연결된 간선 중 클러스터 내부의 합의를 방해하는 간선을 제거한다. 세 번째 방법은 클러스터가 가능한 가장 크게 형성되었음을 보장함으로써 실현된 위상적 클러스터의 유일성을 확보한다. 각 방법은 필요한최소한의간선추가및제거수를정량화하는설계비용과연계되며,총설계비용을최소 화함으로써최적의가상클러스터-루트노드를결정한다.이노드는설계과정에서구조적기준점 역할을 수행한다. 제안된 알고리즘은 최소한의 구조 수정을 통해 설계 목표로 설정된 가상의 클 러스터를 모두 실제 위상적 클러스터로 실현하며, 합의 네트워크가 원하는 위상적 클러스터들로 구성되도록함에있어가장효율적으로설계할수있는방법을제공한다. ©2026 마정 민 ALL RIGHTS RESERVED