A Community-Aware Approach to Minimizing Dissemination in Graphs

Chuxu Zhang, Lu Yu, Chuang Liu, Zi-Ke Zhang, Tao Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given a graph, can we minimize the spread of an entity (such as a meme or a virus) while maintaining the graph’s community structure (defined as groups of nodes with denser intra-connectivity than inter-connectivity)? At first glance, these two objectives seem at odds with each other. To minimize dissemination, nodes or links are often deleted to reduce the graph’s connectivity. These deletions can (and often do) destroy the graph’s community structure, which is an important construct in real-world settings (e.g., communities promote trust among their members). We utilize rewiring of links to achieve both objectives. Examples of rewiring in real life are prevalent, such as purchasing products from a new farm since the local farm has signs of mad cow disease; getting information from a new source after a disaster since your usual source is no longer available, etc. Our community-aware approach, called constrCRlink (short for Constraint Community Relink), preserves (on average) 98.6% of the efficacy of the best community-agnostic link-deletion approach (namely, NetMelt+), but changes the original community structure of the graph by only 4.5%. In contrast, NetMelt+ changes 13.6% of the original community structure.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science
PublisherSpringer Nature
Number of pages15
ISBN (Print)9783319635781
StatePublished - Aug 3 2017


Dive into the research topics of 'A Community-Aware Approach to Minimizing Dissemination in Graphs'. Together they form a unique fingerprint.

Cite this