Identifying Nodes through Neighborhood Signatures

This direction is merged into another direction: unique neighborhood identification. Its last version stays readable and citable here.

Version 1 of 116 papers23 conceptsfrozen 2026-10-04

In traditional network monitoring, the goal is often simple coverage: place enough sensors so that every node is "seen" by at least one sensor. In graph theory, this is known as a dominating set. However, coverage alone is insufficient for diagnosis. If a sensor at node $A$ detects a failure, but both nodes $B$ and $C$ are neighbors of $A$, the system cannot distinguish which of the two is actually failing.

To solve this, researchers have developed the concept of locating-dominating sets. The intuition is to move beyond mere coverage and toward unique identification. By ensuring that every node in a network has a unique "signature" of neighbors within the monitoring set, we can pinpoint the exact location of a fault or a signal.

The Neighborhood as a Fingerprint

The core mechanism of this research direction is the neighborhood signature. In a locating-dominating set, every vertex $v$ not in the set $S$ must be adjacent to a unique subset of $S$.

Imagine a graph where you place sensors on a subset of nodes. If node $X$ is connected to sensors $\{1, 2\}$ and node $Y$ is connected to sensors $\{2, 3\}$, their signatures are distinct. If only sensor 2 triggers, you know there is an ambiguity; if sensors 1 and 2 trigger, you know the source is $X$. As Florent Foucaud and Michael A. Henning describe in Locating-total dominating sets in twin-free graphs: a conjecture, this dual requirement—total coverage plus unique identification—allows for precise fault localization.

The Indistinguishability Problem

Not all graphs allow for perfect identification. If two nodes $u$ and $v$ have the exact same set of neighbors, they are called "twins." No matter where you place your sensors (unless you place one on $u$ or $v$ themselves), these two nodes will always have the same signature.

Because of this, much of the work by Florent Foucaud and colleagues focuses on twin-free graphs. In these structures, every node is theoretically distinguishable. The research then shifts to an efficiency question: what is the minimum number of sensors needed to guarantee that every node has a unique signature?

The Two-Thirds Conjecture

A major focus in this field is determining the upper bounds for these sets. A prominent hypothesis, discussed in Progress towards the two-thirds conjecture on locating-total dominating sets, suggests that for any twin-free graph with $n$ nodes, you never need more than $2n/3$ vertices to form a locating-total dominating set.

Michael A. Henning and Annegret K. Wagler have shown that this bound holds for specific classes like graphs without 4-cycles. This is surprising because it suggests that even with the strict requirement of unique identification, we can still monitor a network using significantly fewer resources than the total number of nodes. In fact, in practical applications like power grids, Yue Zhao and H. Vincent Poor demonstrated in On PMU Location Selection for Line Outage Detection that placing sensors on just one-third of the buses can yield the same detection performance as outfitting the entire grid.

Neighbor-Locating Colorings

The idea of neighborhood-based identification extends beyond dominating sets into graph coloring. In a standard coloring, adjacent nodes must have different colors. In a neighbor-locating coloring, we add a second constraint: every node must be uniquely identified by the set of colors present in its neighborhood.

As explored by Dipayan Chakraborty and Sagnik Sen in On locating and neighbor-locating colorings of sparse graphs, this ensures that no two nodes of the same color share the same "color signature." This is particularly useful in distributed systems where a node might only "see" the types (colors) of its neighbors rather than their specific IDs. By looking at the local distribution of colors, a node can determine its exact position in the global topology.

Why It Works

The power of this research direction lies in the transition from global knowledge to local signatures. By carefully selecting a subset of nodes (or assigning colors), we embed global structural information into local neighborhoods.

  1. Coverage (Domination): Ensures every node is within reach of the monitoring system.
  2. Uniqueness (Location): Ensures the intersection of the neighborhood with the monitoring set is a unique mathematical set for every node.
  3. Efficiency (Bounds): Proves that we can achieve this unique mapping using a fraction of the network's total size, often around $1/2$ to $2/3$ of the vertices.

This framework transforms a network from a collection of identical-looking points into a landscape where every location has a distinct, detectable identity.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_identifying_nodes_through_neighborhood_s_4554c9e5,
  title = {Identifying Nodes through Neighborhood Signatures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/identifying-nodes-through-neighborhood-signatures/rdr_4554c9e578c94b519c14c1afb4dc57f4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_identifying_nodes_through_neighborhood_s_4554c9e5_v1,
  title = {Identifying Nodes through Neighborhood Signatures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/identifying-nodes-through-neighborhood-signatures/rdr_4554c9e578c94b519c14c1afb4dc57f4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}