Influence Spread Control in Complex Networks via Removal of Feed Forward Loops

Abstract

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.

Meeting Name

2021 International Conference on Computer Communications and Networks, ICCCN (2021: Jul. 19-22, Athens, Greece)

Department(s)

Computer Science

Comments

National Science Foundation, Grant CNS-1545037

Keywords and Phrases

Complex Networks; Feed Forward Loop; Influence Diffusion; Motif

International Standard Book Number (ISBN)

978-073811330-2

International Standard Serial Number (ISSN)

1095-2055

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2021 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

22 Jun 2021

Link to Full Text

Share

 
COinS