  Our research problems can be understood with the following metaphor: In
Facebook or Twitter, suppose Mike decides to send a message to a friend Jack,
and Jack next decides to pass the message to one of his own friends Mary, and
the process continues until the current message holder could not find a friend
who is not in the relaying path. How to make the message live longer in the
network with each individual's local decision? Can Mike foresee the length of
the longest paths starting with himself in the network by only collecting
information of native nature? In contrast to similar network problems with
respect to short paths, e.g., for explaining the famous Milgram's small world
experiment, no nontrivial solutions have been proposed for the problems.
  The two research problems are not completely the same and notably our
approach yields solutions to both. We discover node-specific numeric values
which can be computed by only communicating identity-free degree derivatives to
network neighbors and for an arbitrary network node $v$ there exists a function
determining a lower bound for the length of the longest paths starting with it
based on its numeric values. Moreover, in the navigation process initiated at
$v$, inspecting the numeric values of their neighbors, the involved nodes can
independently make their decisions eventually guaranteeing a path of length
longer than the determined lower bound at $v$. Numerical analyses demonstrate
plausible performance of our approach of inferring certain global properties
from local information in complex networks.

Social and Information Networks;Combinatorics;Optimization and Control