Influence Computation in Distributed and Asynchronous Networks

Abstract

본 연구는 각 노드가 자신의 제어에 참조할 이웃 노드를 자율적으로 선택하고, 그 결과 형성된 가중 유향 네트워크에서 분산 프로세싱을 수행하는 자체 형성 분산 비동기 네트워크에서의 영향력 연산 을 다룬다. 엄격한 초기 지역 정보 제약 아래에서 각 노드는 전역 그래프 정보를 사전에 가정하는 대신, 이웃노드와의통신을통해그래프관련노드기준네트워크파라미터를획득해야한다.본연구는이러한 요구를 프로세스 기반 분산 네트워크 파라미터 측정 문제로 정식화하고, 이 문제의 영향력 연산에 대한 구체적 사례로서 분산 영향력 연산 프로세싱(distributed influence computation processing, DICP)에 집중한다. DICP에서는각노드의조상집합과그에대응하는 0이아닌내측영향력값들을노드기준목적네트 워크 파라미터로 설정한다. 이들의 효율적인 분산 연산을 위하여, 영향력 구조를 컨센서스 동역학 모델을 통해 해석하고 이를 지역 영향력과 내적 영향력 성분으로 재정식화한다. 지역 그래프에 기반한 이러한 재정식화는추종자측지역영향력연산과지도자측내적영향력연산을분리함으로써,역할의존적노드 동작과 노드 기준 영향력 연산을 위한 기반을 제공한다. 또한 본 연구는 특히 지역 영향력 연산에서 수렴 속도와 연산 효율을 향상시키기 위하여 벡터화 스텝 컨센서스 동역학(VSCD)을 적용한다. 이와같은정식화를바탕으로,분산영향력연산프로세싱은프로세싱알고리즘(processing algorithm, PA)과 그 모듈러 알고리즘(modular algorithm, MA) 족으로 구성된다. 모듈러 알고리즘 족은 분산 리더 집합 식별, 지역 영향력 측정, 성분별 스텝 사이즈 측정, 내적 영향력 측정, 유효 영향력 연산으로 구성된 다. 이러한 모듈러 알고리즘들은 리더 집합 식별이 분기 조건을 제공하고, 지역 영향력 및 내적 영향력 연산부가 분리된 영향력 관련 파라미터를 연산하며, 최종 통합이 각 노드의 추정 조상 집합과 그에 대응 하는 0이 아닌 내측 영향력 부분벡터를 반환하는 분할-연산-통합 구조를 실현한다. 따라서 DICP는 분산 비동기 네트워크에서의 영향력 연산을 위한 전이별 모듈러 알고리즘 족을 갖는 완전 의사코드 프로세싱 알고리즘으로 구현된다. DICP의 구현은 본 연구에서 제안하는 분산 네트워크 파라미터 측정 프로세싱(distributed network- parameter measurement processing, DNPMP) 프레임워크에 기반한다. 프로세싱 알고리즘 수준에서는, 토큰–키 일관적인 분산 키활성화 페트리넷(DKPN) 구체화를 사용하여 사용 가능한 지역 정보와 반환된 목적 파라미터로부터 모듈러 알고리즘들이 언제 시작될 수 있는지와, 프로세싱 알고리즘이 그 모듈러 알고리즘 족을 조정한 뒤 최종 목적 파라미터를 어떻게 반환할 수 있는지를 분석한다. 모듈러 알고리즘 수준에서는, 결정 타입 반영 초기-활성-결정-종료 상태 전이 모델(DTA-IADT)과 반복적 헤더 및 데이터 요청 기법(RRHD)을 통해 비동기 이웃 노드 통신, 목적 파라미터 결정, 완전 반환성을 갖는 조기 종료, 최종 응답 처리를 위한 완전 의사코드 구조를 제공한다. 특히 최종 응답 및 지시 최종 응답 메커니즘은 결정된 모듈러 알고리즘들이 이웃 노드의 목적 파라미터 결정과 조기 종료를 지원할 수 있도록 하며, 프 로세싱 알고리즘 수준의 최종 응답 보존과 키 활성화 기반 모듈러 알고리즘 실행은 전체 분산 프로세스의 완전반환성을유지하도록한다.결과적으로제안된분산네트워크파라미터측정프로세싱프레임워크는 개별모듈러알고리즘들과프로세싱알고리즘이관리하는전체분산프로세스모두에대해완전반환성을 갖는 조기 종료를 지원한다. 제안된 모듈러 알고리즘들은 이론적 결과를 통해 엄밀하게 분석되었으며, 시뮬레이션 결과를 통해 벡터화 스텝 컨센서스 동역학 기반 지역/내적 영향력 정식화의 수렴 특성과 제안된 DICP 구현의 비동기 진행, 결정 메커니즘, 최종 응답 처리, 최종 추정 목적 네트워크 파라미터가 검증되었다. 따라서 본 연구는 자체 형성 분산 비동기 네트워크에서의 영향력 연산을 위한 프로세스 지향 설계 기반을 제공하며, 이를 통해 엄격한 초기 지역 정보 제약 아래에서 후속 분산 알고리즘을 지원한다.|This study addresses influence computation in self-constructed distributed and asynchronous networks, in which each node autonomously selects its reference neighbors and performs distributed processing over the resulting weighted directed network. Under strict initial local-information con- straints, each node must obtain graph-related node-wise network parameters through neighboring-node communication rather than assuming global graph information in advance. This study formulates this requirement as a process-based distributed network-parameter measurement problem and focuses on distributed influence computation processing (DICP) as the influence-computation instance of this problem. In DICP, the ancestor set of each node and the corresponding nonzero incoming influence val- ues are selected as the node-wise objective network parameters. To support their efficient distributed computation, the influence structure is analyzed through a consensus-dynamics model and reformu- lated into regional and internal influence components. The regional-graph-based reformulation pro- vides the basis for role-dependent node operation and node-wise influence computation by separating follower-side regional-influence computation from leader-side internal-influence computation. In addi- tion, vector-wise step-sized consensus dynamics (VSCD) is applied to improve convergence speed and computational efficiency, particularly in regional-influence computation. Based on this formulation, DICP is organized as a processing algorithm (PA) and its family of mod- ular algorithms (MAs). The modular algorithm family consists of distributed leader-set identification, regional-influence measurement, component step-size measurement, internal-influence measurement, and valid-influence computation. These MAs realize a divide–computation–integration structure in which leader-set identification provides the divide condition, the regional- and internal-influence com- putation parts compute separated influence-related parameters, and the final integration returns the estimated ancestor set and the corresponding nonzero incoming influence subvector of each node. Thus, DICP is realized as a full pseudo-code processing algorithm with a transition-wise modular algorithm family for influence computation over distributed and asynchronous networks. The realization of DICP is based on the proposed distributed network-parameter measurement processing (DNPMP) framework. At the PA level, a token–key consistent distributed key-augmented Petri net (DKPN) specification is used to analyze when MAs can be started from available local information and returned objective parameters, and how the PA can return its final objective param- eters after coordinating its MA family. At the MA level, the determination-type-augmented initial- active-determination-terminated state-transition model (DTA-IADT state-transition model) and the repeatedly requesting headers and data (RRHD) methodology provide full pseudo-code structures for asynchronous neighboring-node communication, objective-parameter determination, early termination with full returnability, and final-response handling. In particular, final-response and instruction-final- response mechanisms allow determined MAs to support neighboring objective-parameter determina- tion and early termination, while PA-level final-response preservation and key-enabled MA execution preserve full returnability of the overall distributed process. Consequently, the proposed DNPMP framework supports early termination with full returnability both for individual MAs and for the PA-managed distributed process. The proposed MAs are rigorously analyzed through theoretical results, and simulation results validate the convergence behavior of the VSCD-based regional/internal influence formulation as well as the asynchronous progression, determination mechanisms, final-response handling, and final esti- mated objective network parameters of the proposed DICP implementation. Therefore, this study provides a process-oriented design basis for influence computation on self-constructed distributed and asynchronous networks and supports subsequent distributed algorithms under strict initial local- information constraints.