Influence Spread Control in Complex Networks via Removal of Feed Forward Loops
Selective removal of certain subgraphs called motifs based on the spread function value is one of the most powerful approaches to curb the overall influence spread in any complex network. In this paper, we first prove that any general spread function preserves both monotonicity and submodularity properties even under motif removal operations. Next, we propose a scoring mechanism as a novel spread function that quantifies the relative importance of a given motif within the overall influence spread dynamics on the complex network. We design a novel algorithm that eliminates motifs with high spread scores to curb influence spread. We evaluate the performance of our proposed spread control algorithm using simulation experiments in the context of 3-node motifs called feed forward loops (FFLs) in both real and synthetic network topologies. We demonstrate that high-scoring motifs intercept a high number of short paths from the pre-assigned source and sinks, because of which their elimination results in a significant effect on curbing the influence spread. Furthermore, we empirically evaluate the run-time and cost versus performance trade-off of the proposed algorithm.
S. Roy et al., "Influence Spread Control in Complex Networks via Removal of Feed Forward Loops," Proceedings of the International Conference on Computer Communications and Networks (2021, Athens, Greece), Institute of Electrical and Electronics Engineers (IEEE), Jun 2021.
The definitive version is available at https://doi.org/10.1109/ICCCN52240.2021.9522280
2021 International Conference on Computer Communications and Networks, ICCCN (2021: Jul. 19-22, Athens, Greece)
Keywords and Phrases
Complex Networks; Feed Forward Loop; Influence Diffusion; Motif
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 2021 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
22 Jun 2021