Impact neighborhood indexing (INI) in diffusion graphs

Jung Hyun Kim, Kasim Candan, Maria Luisa Sapino

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

2 Scopus citations


A graph neighborhood consists of a set of nodes that are nearby or otherwise related to each other. While existing definitions consider the structure (or topology) of the graph, we note that they fail to take into account the information propagation and diffusion characteristics, such as decay and reinforcement, common in many networks. In this paper, we first define the propagation efficiency of nodes and edges. We use this to introduce the novel concept of zero-erasure (or impact) neighborhood (ZEN) of a given node, n, consisting of the set of nodes that receive information from (or are impacted by) n without any decay. Based on this, we present an impact neighborhood indexing (INI) algorithm that creates data structures to help quickly identify impact neighborhood of any given node. Experiment results confirm the efficiency and effectiveness of the proposed INI algorithms.

Original languageEnglish (US)
Title of host publicationCIKM 2012 - Proceedings of the 21st ACM International Conference on Information and Knowledge Management
Number of pages5
StatePublished - 2012
Event21st ACM International Conference on Information and Knowledge Management, CIKM 2012 - Maui, HI, United States
Duration: Oct 29 2012Nov 2 2012

Publication series

NameACM International Conference Proceeding Series


Other21st ACM International Conference on Information and Knowledge Management, CIKM 2012
Country/TerritoryUnited States
CityMaui, HI


  • graph neighborhood
  • impact propagation
  • indexing

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Impact neighborhood indexing (INI) in diffusion graphs'. Together they form a unique fingerprint.

Cite this