Distributed graph-based topology adaptation using motif signatures

Michael Stein, Karsten Weihe, Augustin Wilberg, Roland Land Kluge, Julian M. Klomp, Mathias Schnee, Lin Wang, Max Mühlhäuser

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


A motif is a small graph pattern, and a motif signature counts the occurrences of selected motifs in a network. The motif signature of a real-world network is an important characteristic because it is closely related to a variety of semantic and functional aspects. In recent years, motif analysis has been successfully applied for adapting topologies of communication networks: The motif signatures of very good networks (e.g., in terms of load balancing) are determined a priori to derive a target motif signature. Then, a given network is adapted in iterative steps, subject to side constraints and in a distributed way, such that its motif signature approximates the target motif signature. In this paper, we formalize this adaptation problem and show that it is NP-hard. We present LoMbA, a generic approach for motif-based graph adaptation: All types of networks, all selections of motifs, and all types of consistency-maintaining constraints can be incorporated. To evaluate LoMbA, we conduct a simulation study based on several scenarios of topology adaptation from the domain of communication networks. We consider topology control in wireless ad-hoc networks, balancing of video streaming trees, and load balancing of peer-to-peer overlays. In each considered application scenario, the simulation results are remarkably good, although the implementation was not tuned toward these scenarios.

Original languageEnglish
Title of host publication19th Workshop on Algorithm Engineering and Experiments 2017, ALENEX 2017
EditorsSandor Fekete, Vijaya Ramachandran
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages12
ISBN (Electronic)9781611974768
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event19th Workshop on Algorithm Engineering and Experiments 2017, ALENEX 2017 - Barcelona, Spain
Duration: 17 Jan 201718 Jan 2017

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
ISSN (Print)2164-0300


Conference19th Workshop on Algorithm Engineering and Experiments 2017, ALENEX 2017


Dive into the research topics of 'Distributed graph-based topology adaptation using motif signatures'. Together they form a unique fingerprint.

Cite this