1. Graph Similarity-Based Maximum Stable Subgraph Extraction of Information Topology From a Vehicular Network
- Author
-
Xinyi Liu, He Huang, Liang Dai, and Yun Meng
- Subjects
Dynamic network analysis ,Optimization problem ,Computer science ,business.industry ,Mechanical Engineering ,Stability (learning theory) ,Control reconfiguration ,Topology (electrical circuits) ,Topology ,Computer Science Applications ,Network management ,Automotive Engineering ,Graph (abstract data type) ,Overhead (computing) ,business - Abstract
Information topology graph has been extensively used in modeling network management, where it is necessary to continually optimize the management of the dynamic network. However, frequent reconfiguration may lead to an increased overhead and a degraded latency. Since the mobility in a vehicular network is restricted by the road, there is an internal relatively stable part embedded in the entire dynamic network. Thus, in this study, this characteristic is first used to reduce reconfiguration, where the maximum stable subgraph is extracted and configuration only needs to be reconsidered for the rest of the network. However, there are three main challenges in the modeling and solving procedure, namely the evaluation of stability of part of the network, the assurance of the coherence in the set of extracted vehicles and the huge computation complexity of the subgraph enumeration. Therefore, in this study, first, the vehicular network is modeled by constructing the time-evolving information topology graph, in which a subgraph similarity is constructed to quantify the stability of part of network. Second, a maximum stable subgraph extraction optimization problem is presented, where the coherence constraint of vehicles is proposed. Finally, a gradual contraction extraction algorithm is proposed to solve the optimization problem with a low complexity. The simulation results reveal that the proposed algorithm can extract a stable subgraph with an approximate maximum size, and has a higher adaptability than the compared ones. Furthermore, it was found that the application of the proposed algorithm in resource allocation can effectively reduce the reconfiguration.
- Published
- 2022