  Selecting the most influential agent in a network has huge practical value in
applications. However, in many scenarios, the graph structure can only be known
from agents' reports on their connections. In a self-interested setting, agents
may strategically hide some connections to make themselves seem to be more
important. In this paper, we study the incentive compatible (IC) selection
mechanism to prevent such manipulations. Specifically, we model the progeny of
an agent as her influence power, i.e., the number of nodes in the subgraph
rooted at her. We then propose the Geometric Mechanism, which selects an agent
with at least 1/2 of the optimal progeny in expectation under the properties of
incentive compatibility and fairness. Fairness requires that two roots with the
same contribution in two graphs are assigned the same probability. Furthermore,
we prove an upper bound of 1/(1+\ln 2) for any incentive compatible and fair
selection mechanisms.
