Gossip: Identifying Central Individuals in a Social Network
Abhijit Banerjee$^{\dagger
Arun G. Chandrasekhar$^{\ddagger
Esther Duflo$^{\S
Matthew O. Jackson$^{\star
Can we identify the members of a community who are best-placed to diffuse information simply by asking a random sample of individuals? We show that boundedly-rational individuals can, simply by tracking sources of gossip, identify those who are most central in a network according to ``diffusion centrality,'' which nests other standard centrality measures. Testing this prediction with data from 35 Indian villages, we find that respondents accurately nominate those who are diffusion central (not just those with many friends). Moreover, these nominees are more central in the network than traditional village leaders and geographically central individuals. \textsc{JEL Classification Codes: D85, D13, L14, O12, Z13 \textsc{Keywords: Centrality, Gossip, Networks, Diffusion, Influence, Social Learning
bcdjgossip_Aug-11_2014.tex
\documentclass[12pt, oneside]{amsart}
%%%%%%%%%%%%%%---%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage[T1]{fontenc}
\pdfoutput=1
\usepackage{geometry}
\geometry{verbose,tmargin=1.5in,bmargin=1.5in,lmargin=1.5in,rmargin=1.5in}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{comment}
\usepackage{color}
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{soul}
\usepackage[countmax]{subfloat}
\usepackage{float}
\usepackage{rotfloat}
\usepackage{setspace}
\usepackage{esint}
\onehalfspacing
%\doublespacing
\usepackage[authoryear]{natbib}
\definecolor{MyDarkBlue}{rgb}{0,0.08,0.45}
\usepackage[unicode=true,pdfusetitle, bookmarks=true,bookmarksnumbered=false,bookmarksopen=false, breaklinks=false,pdfborder={0 0 1},backref=section,colorlinks=true, linkcolor = MyDarkBlue, citecolor = MyDarkBlue]{hyperref}
\usepackage{breakurl}
\usepackage[para]{threeparttable}



\PassOptionsToPackage{normalem}{ulem}
\usepackage{ulem}

\makeatletter

\numberwithin{equation}{section}

\hypersetup{colorlinks=true, linkcolor=MyDarkBlue}



\newtheorem{claim}{{\bf \sc Claim}}
\newtheorem{theorem}{{\bf\sc Theorem}}
\newtheorem{lemma}{{\bf\sc Lemma}}
\newtheorem{example}{{\bf\sc Example}}
\newtheorem{corollary}{{\bf\sc Corollary}}
\newtheorem{conjecture}{{\bf\sc Conjecture}}
\newtheorem{proposition}{{\bf\sc Proposition}}
\newtheorem{rem}{{\bf \sc Remark}}
\newtheorem{alg}{{\bf\sc Algorithm}}

\newtheorem{thm}{{\bf \sc Theorem}}[section]
\newtheorem{lem}{{\bf \sc Lemma}}[section]
\newtheorem{cor}{{\bf\sc Corollary}}[section]
\newtheorem{prop}{{\bf\sc Proposition}}[section]




\DeclareMathOperator*{\plim}{plim}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\cvgto}{\stackrel{\mathrm{P}}{\longrightarrow}}
\DeclareMathOperator*{\wkto}{\rightsquigarrow}
\providecommand{\E}{\mathrm{E}}
\providecommand{\var}{\mathrm{var}}
\providecommand{\Bin}{\mathrm{Bin}}
\providecommand{\corr}{\mathrm{corr}}
\providecommand{\cov}{\mathrm{cov}}
\providecommand{\aut}{\mathrm{aut}}
\providecommand{\Skew}{\mathrm{Skew}}
\providecommand{\Prob}{\mathrm{P}}
\providecommand{\thetahat}{\widehat{\theta}}
\providecommand{\gammahat}{\widehat{\gamma}}
\providecommand{\betahat}{\widehat{\beta}}
\providecommand{\phat}{\widehat{p}}
\providecommand{\Stil}{\widetilde{S}}
\renewcommand{\Pr}{\Prob}
\providecommand{\g}{{\bf g}}
\providecommand{\bfH}{{\bf H}}
\providecommand{\bfv}{{\bf v}}
\def\Re{\mathbb{R}}
\def\eproof{\hbox{\hskip3pt\vrule width4pt height8pt depth1.5pt}}
\renewenvironment{proof}[1][Proof]{\noindent\text{#1.} }{\ \rule{0.5em}{0.5em}}


\makeatother

\begin{document}

\title{Gossip: Identifying Central Individuals in a Social Network}



\author{Abhijit Banerjee$^{\dagger}$ }
\author{Arun G. Chandrasekhar$^{\ddagger}$}
\author{Esther Duflo$^{\S}$ }
\author{Matthew O. Jackson$^{\star}$ }
\date{This Version: August 2014}


\thanks{Ben Golub, Michael Dickstein and participants at various seminars/conferences
provided helpful comments. Financial support from the NSF under grants
SES-1156182 and SES-1155302, from the AFOSR and DARPA under grant
FA9550-12-1-0411, and from ARO MURI under award No. W911NF-12-1-0509
is gratefully acknowledged. We thank Francisco Mu\~noz for excellent
research assistance. We are grateful to CMF at IFMR, Tanay Balantrapu,
Gowri Nagraj, and Manaswini Rao.}
\thanks{$^{\dagger}$Department of Economics, MIT}
\thanks{$^{\ddagger}$Department of Economics, Stanford University}
\thanks{$^{\S}$Department of Economics, MIT}
\thanks{$^{\star}$Department of Economics, Stanford University; Santa Fe Institute; and CIFAR}


\begin{abstract}
Can we identify the members of a community who are best-placed to
diffuse information simply by asking a random sample of individuals?
We show that boundedly-rational individuals can, simply by tracking
sources of gossip, identify those who are most central in a network
according to ``\emph{diffusion centrality},'' which nests other
standard centrality measures. Testing this prediction with data from
35 Indian villages, we find that respondents accurately nominate those
who are diffusion central (not just those with many friends). Moreover,
these nominees are more central in the network than traditional village
leaders and geographically central individuals.


\textsc{JEL Classification Codes:} D85, D13, L14, O12, Z13

\textsc{Keywords:} Centrality, Gossip, Networks, Diffusion, Influence, Social Learning
\end{abstract}


\maketitle
\newpage

\section{Introduction}

\begin{quote} \emph{``The secret of my influence has always been that it remained secret.''}
-- Salvador Dal\'{i}
\end{quote}

\

Knowing who is influential, or central, in a community, can be important
for the community's members as well as for businesses and policymakers.
In particular, the extent to which a piece of information diffuses
among a population often depends on how central the initially informed
are within the network (see \citet*{katzl1955,rogers1995,kempekt2003,kempekt2005,borgatti2005,ballestercz2006,banerjeecdj2013}).
Policymakers and organizations can thus benefit from targeting the
right individuals in efforts to effectively spread valuable information.

However, learning who is central in a social network has the potential
to be difficult. For policymakers, collecting detailed network data
is costly. Even for members of the community, knowing the structure
of the network beyond their immediate friends is far from automatic.
Do people know how central other people, outside of their immediate
circle, are? In this paper, we answer this question theoretically
and empirically.

First, we develop a simple model, building upon our previous work
\citep*{banerjeecdj2013}, to show that individuals in a network should
be able to identify central individuals within their community \emph{without
knowing anything about the structure of the network}. Our model is
about a process we call gossip, where nodes generate pieces of information
that are then stochastically passed from neighbor to neighbor. We
assume that individuals who hear the gossip are able to keep count
of the number of times each person in the network get mentioned.%
\footnote{We use the term ``gossip'' to refer to the spreading of information
about particular people. Our diffusion process is focused on basic
information that is not subject to the biases or manipulations that
might accompany some ``rumors'' (e.g., see \citet*{blochdk2014}).%
} We show that for any listener in the network, the relative ranking
under this count converges over time to the correct ranking of every
node's ability to send information to the rest of the network. The
specific measure of a node's ability to send information that we use
is given by the ``diffusion centrality,'' introduced in \citet{banerjeecdj2013}
which answers the question of how widely information from a given
node diffuses in a given number of time periods and for a given random
per period transmission probability. We relate diffusion centrality
to other standard measures of centrality in the literature, proving
that it nests three of the most prominent measures: degree centrality
at one extreme (if there is just one time period of communication),
and eigenvector centrality and Katz-Bonacich centrality at the other
extreme (if there are unlimited periods of communication). For intermediate
numbers of periods diffusion centrality takes on a wide range of other
values.

In other words, by listening and keeping count of how often they hear
\emph{about} someone, individuals learn the correct ranking of community
members from the point of view of how effectively they can serve as
a source of information to the rest of the community.

Second, we use a unique dataset to assess whether this holds empirically.
We asked every adult in each of 35 villages to name the person in
their village best suited to initiate the spread of information. We
combine their answers (which we call their ``nominations'') with
detailed network data that include maps of a variety of interactions
in each of the 35 villages. We show that individuals nominate highly
diffusion/eigenvector central people (on average at the 71st percentile
of centrality). We also show that the nominations are not simply based
on the nominee's leadership status or geographic position in the village,
but are significantly correlated with diffusion centrality even after
conditioning on these characteristics, and are better predictors of
centrality than these characteristics. This suggests that people
understand our questions and are doing more than simply naming traditional
leaders or geographically central individuals. Furthermore, there
is suggestive evidence that they nominate people who are indeed diffusion
central, not only people with many friends.

In sum, our model shows how individuals can learn who are the most
central people in their network, and our empirical work suggests that
individuals have learned this (although, of course, the data could
be consistent with other models of how people choose individuals to
nominate). To our knowledge, this is the first paper to demonstrate
that members of communities are able, easily and accurately, to identify
highly central people in their community. It is also the first to
describe a simple process by which people can learn things about part
of their broader network that may intuitively seem outside their ambit.%
\footnote{There are some papers (e.g., \citet{milgram1967} and \citet{doddsmw2003})
that have checked people's abilities to use knowledge of their friends'
connections to efficiently route messages to reach distant people,
but those rely on local knowledge.%
} This is a result of practical importance, since asking people who
is the best person to spread information is a much cheaper way to
collect this information than collecting data on the entire network.

\

\section{A Model of Network Communication}\label{sec:model}

We consider the following model.


\subsection{A Network of Individuals}

A society of $n$ individuals are connected via a possibly directed%
\footnote{When defining $\g$ in the directed case, the $ij$-th entry should
indicate that $i$ can tell something to $j$. In some networks, this
may not be reciprocal. %
} and weighted network, which has an adjacency matrix ${\bf g}\in\{0,1\}^{n\times n}$.
Unless otherwise stated, we take the network $\g$ to be fixed and
let $v^{(1)}$ be its first (right-hand) eigenvector, corresponding
to the largest eigenvalue $\lambda_{1}$.%
\footnote{$v^{(1)}$ is such that ${\bf g}{v}^{(1)}=\lambda_{1}{v}^{(1)}$ where
$\lambda_{1}$ is the largest eigenvalue of ${\bf g}$ in magnitude.%
} The first eigenvector is nonnegative and real-valued by the Perron-Frobenius
Theorem.

Throughout, we assume that the network is (strongly) connected in
that there exists a (directed) path from every node to every other
node, so that information originating at any node could potentially
make its way eventually to any other node.%
\footnote{More generally, everything we say applies to the components of the
network.%
}


\subsection{Diffusion Centrality}

\
 \citet{banerjeecdj2013} defined a notion of centrality called \emph{diffusion
centrality}, based on random information flow through a network according
to the following process, which is a variation of a standard diffusion
process that underlies many contagion models.%
\footnote{See \citet{jacksony2011} for background and references. A continuous
time version of diffusion centrality appears in \citet{lawyer2014}.%
}

A piece of information is initiated at node $i$ and then broadcast
outwards from that node. In each period, each informed node informs
each of its neighbors of the piece of information and the identity
of its original source with a probability $p\in(0,1]$, independently
across neighbors and history. The process operates for $T$ periods,
where $T$ is a positive integer.

There are many reasons to allow $T$ to be finite. For instance, a
new piece of information may only be ``news'' for a limited time.
Because of boredom, arrival of other news, the topic of conversation
may change. By allowing for a variety of $T$'s, diffusion centrality
admits important finite-horizon cases, as well as more extreme cases
where agents discuss a topic indefinitely.%
\footnote{Of course this is an approximation and, moreover, different topics
may have different $T$'s. The current model and definition already
moves beyond the literature, but even richer models could also be
studied.%
}

Diffusion centrality measures how extensively the information spreads
as a function of the initial node. In particular, let 
\[
{\bf H}({\bf g};p,T):=\sum_{t=1}^{T}\left(p{\bf g}\right)^{t},
\]
be the ``hearing matrix.'' The $ij$-th entry of ${\bf H}$, $H({\bf g};p,T)_{ij}$,
is the expected number of times, in the first $T$ periods, that $j$
hears about a piece of information originating from $i$. Diffusion
centrality is then defined by 
\[
{DC}({\bf g};p,T):={\bf H}({\bf g};p,T)\cdot{\bf 1}=\left(\sum_{t=1}^{T}\left(p{\bf g}\right)^{t}\right)\cdot{\bf 1}.
\]


So, ${DC}({\bf g};p,T)_{i}$ is the expected total number of times
that some piece of information that originates from $i$ is heard
by any of the members of the society during a $T$-period time interval.%
\footnote{ We note two useful normalizations. One is to compare it to what would
happen if $p=1$ and ${\bf g}$ were the complete network ${\bf g}^{c}$,
which produces the maximum possible entry for each $ij$ subject to
any $T$. Thus, each entry of ${DC}({\bf g};p,T)$ could be divided
through by the corresponding entry of ${DC}({\bf g}^{c};1,T)$. This
produces a measure for which every entry lies between 0 and 1, where
1 corresponds to the maximum possible numbers of expected paths possible
in $T$ periods with full probability weight and full connectedness.
Another normalization is to compare a given node to the total level
for all nodes; that is, to divide all entries of ${DC}({\bf g};p,T)$
by $\sum_{i}{DC}_{i}({\bf g};p,T)$. This normalization tracks how
relatively diffusive one node is compared to the average diffusiveness
in its society. %
} 
 \citet{banerjeecdj2013}
showed that diffusion centrality was a statistically significant predictor
of the spread of information -- in that case, about a microfinance
program.

Note that this measure allows people to hear the information multiple
times from the same person and count those times as distinct reports,
so that it is possible for an entry of $DC$ to be more than $n$.
There are several advantages to defining it in this manner. First,
although it is possible via simulations to calculate a measure that
tracks the expected number of informed nodes and avoids double-counting,
this expression is \emph{much} easier to calculate and for many parameter
values the two measures are roughly proportional to each other. Second,
this version of the measure relates nicely to other standard measures
of centrality in the literature, while a measure that adjusts for
multiple hearing does not. Third, in a world in which multiple hearings
lead to a greater probability of information retention, this count
might actually be a better measure of what people learn.%
\footnote{One could also further enrich the measure by allowing for the forgetting
of information, but with three parameters the measure would start
to become unwieldy.%
}



\subsection{Diffusion Centrality's Relation to Other Centrality Measures}

It is useful to situate diffusion centrality relative to other prominent
measures of centrality in the literature.

Let $d({\bf g})$ denote degree centrality (so $d_{i}({\bf g})=\sum_{j}g_{ij}$).
Eigenvector centrality corresponds to $v^{(1)}({\bf g})$: the first
eigenvector of ${\bf g}$. Also, let $KB({\bf g},p)$ denote Katz-Bonacich
centrality -- defined for $p<1/\lambda_{1}$ by:%
\footnote{See (2.7) in \citet{jackson2008} for additional discussion and background.
This was a measure first discussed by Katz, and corresponds to Bonacich's
definition when both of Bonacich's parameters are set to $p$.%
} 
\[
KB(p,{\bf g}):=\left(\sum_{t=1}^{\infty}\left(p{\bf g}\right)^{t}\right)\cdot{\bf 1}.
\]


It is direct to see that (i) diffusion centrality is proportional
to degree centrality at the extreme at which $T=1$, and (ii) if $p<1/\lambda_{1}$,
then diffusion centrality coincides with Katz-Bonacich centrality
if we set $T=\infty$. We now show that when $p>1/\lambda_{1}$ diffusion
centrality approaches eigenvector centrality as $T$ approaches $\infty$,
which then completes the picture of the relationship between diffusion
centrality and extreme centrality measures.

The difference between the extremes of Katz-Bonacich centrality and
eigenvector centrality depends on whether $p$ is sufficiently small
so that limited diffusion takes place even in the limit of large $T$,
or whether $p$ is sufficiently large so that the knowledge saturates
the network and then it is only relative amounts of saturation that
are being measured.%
\footnote{Saturation occurs when the entries of $\left(\sum_{t=1}^{\infty}\left(p{\bf g}\right)^{t}\right)\cdot{\bf 1}$
diverge (note that in a {[}strongly{]} connected network, if one entry
diverges, then all entries diverge). Nonetheless, the limit vector
is still proportional to a well defined limit vector: the first eigenvector.%
}

\begin{theorem} \label{DC}

\
 
\begin{enumerate}
\item Diffusion centrality is proportional to degree when $T=1$: 
\[
{DC}\left({\bf g};p,1\right)=pd\left({\bf g}\right).
\]

\item If $p\geq1/\lambda_{1}$, then as $T\rightarrow\infty$ diffusion
centrality approximates eigenvector centrality: 
\[
\lim_{T\rightarrow\infty}\frac{1}{\sum_{t=1}^{T}\left(p\lambda_{1}\right)^{t}}{DC}\left({\bf g};p,T\right)={\bf v}^{(1)}.
\]

\item For $T=\infty$ and $p<1/\lambda_{1}$, diffusion centrality is Katz-Bonacich
centrality: 
\[
{DC}\left({\bf g};p,\infty\right)=KB\left({\bf g},p\right);\ \ p<1/\lambda_{1}.
\]

\end{enumerate}
\end{theorem}

All proofs appear in the Appendix.

The result shows that as $T$ is varied, diffusion centrality nests
three of the most prominent and used centrality measures: degree centrality,
eigenvector centrality, and Katz-Bonacich centrality. It thus provides
a foundation for these measures and spans between them.%
\footnote{This formalizes a result we mention in \citep*{banerjeecdj2013}.
An independent formalization appears in \citet{benzik2014}.%
}$^{,}$ %
\footnote{We also remark on the comparison to another measure: the influence
vector that appears in the DeGroot learning model (see, e.g., \citet{golubj2010}).
That metric captures how influential a node is in a process of social
learning. It corresponds to the (left-hand) unit eigenvector of a
stochasticized matrix of interactions rather than a raw adjacency
matrix. While it might be tempting to use that metric here as well,
we note that it is the right conceptual object to use in a process
of \emph{repeated averaging} through which individuals update opinions
based on averages of their neighbors' opinions. It is thus conceptually
different from the diffusion process that we study. One can define
a variant of diffusion centrality that works for finite iterations
of DeGroot updating.%
} Between these extremes, diffusion centrality measures how diffusion
process operates for some limited number of periods. Importantly,
as in \citet{banerjeecdj2013}, the behavior in the intermediate ranges
can be more relevant for certain diffusion phenomena.

\

\section{Relating Diffusion Centrality to Network Gossip}\label{sec:gossip}


We now investigate whether and how individuals living in ${\bf g}$
end up with knowledge of others' positions in the network that correlates
with diffusion centrality without knowing anything about the network
structure.


\subsection{A Gossip Process}

Diffusion centrality considers diffusion from the \emph{sender's}
perspective. Let us now consider the same stochastic information diffusion
process but from a \emph{receiver's} perspective. Over time, each
individual hears information that originates from different sources
in the  network, and in turn randomly pass that information
on. The society discusses each of these pieces
of information for $T$ periods. The key point is that there are many
such topics of conversation, originating from all of the different
individuals in the society, with each topic being passed along for
$T$ periods.

For instance, Arun may tell Matt that he has a new car. Matt then
may tell Abhijit that ``Arun has a new car,'' and then Abhijit may
tell Esther that ``Arun has a new car.'' Arun may also have told
Ben that he thinks house prices will go up and Ben could have told
Esther that ``Arun thinks that house prices will go up''. In this
model Esther keeps track of the cumulative number of times that bits
of information that originated from Arun reach her and compares it
with the same number for information that originated from other people.
What is crucial therefore is that the news involves the name of the
node of origin -- in this case ``Arun'' -- and not what the information
is about. The first piece of news originating from Arun could be about
something he has done (``bought a car'') but the second could just
be an opinion (``Arun thinks house prices will go up''). Esther
keeps track of the fact that she has heard two different pieces of
information originating from Arun.



Recall that 
\[
{\bf H}({\bf g};p,T)=\sum_{t=1}^{T}\left(p{\bf g}\right)^{t},
\]
is such that the $ij$-th entry, $H({\bf g};p,T)_{ij}$, is the expected
number of times $j$ hears a piece of information originating from
$i$.

We define the \emph{network gossip heard} by node $j$ to be the $j$-th
column of ${\bf H}$, 
\[
NG({\bf g};p,T)_{j}:=H({\bf g};p,T)_{\cdot j}.
\]
Thus, $NG_{j}$ lists the expected number of times a node $j$ will
hear a given piece of news as a function of the node of origin of
the information. So, if $NG({\bf g};p,T)_{ij}$ is twice as high as
$NG({\bf g};p,T)_{kj}$ then $j$ is expected to hear news twice as
often that originated at node $i$ compared to node $k$, presuming
equal rates of news originating at $i$ and $k$.

Note the different perspectives of $DC$ and $NG$: diffusion centrality
tracks how well information spreads from a given node, while network
gossip tracks relatively how often a given node hears information
from (or about) each of the other nodes.

To end this sub-section two remarks are in order. First, one could
allow passing probabilities to differ by information type and pairs
of nodes.%
\footnote{We can generalize our setup replacing $p$ with a matrix ${\bf P}$.
Now define 
\[
{\bf H}({\bf g};{\bf P},T):=\left(\sum_{t=1}^{T}\left({\bf P}\circ{\bf g}\right)^{t}\right).
\]
Here ${\bf P}$ can have entries $P_{ij}$ which allow the transmission
probabilities to vary by pair. Note that $P_{ij}$ can depend on characteristics
of those involve and encode strategic behavior based on the economics
being modeled.%
} Indeed, in \citet{banerjeecdj2013} we allowed different nodes to
pass information with different probabilities, and in \citet{banerjeebcdj2014}
we allow the probability of communication to depend on the listener's
network position. Although one can enrich the model in many ways to
capture specifics of information passing, this simple version captures
basic dynamics and relates naturally to centrality measures. Second,
we could allow nodes to differ in how frequently they generate new
information which is then transmitted to its neighbors. Provided this
transmission rate is positively related to nodes' centralities, the
results that we present below still hold (and, in fact, the speed
of convergence would be increased).


\subsection{Identifying Central Individuals}

With this measure of gossip in hand, we show how individuals in a
society can estimate who is central simply by counting how often they
hear gossip about others. We first show that, on average, individuals'
rankings of others according to how much gossip they hear about the
others, given by $NG_{j}$, are positively correlated with diffusion
centrality.

\begin{theorem} \label{prop:cov} For any $({\bf g};p,T)$, $\sum_{j}\cov(DC({\bf g};p,T),NG({\bf g};p,T)_{j})=\var(DC)$.
Thus, in any network with differences in diffusion centrality among
individuals, the average covariance between diffusion centrality and
network gossip is positive. \end{theorem}

It is important to emphasize that although both measures, $NG_{i}$
and $DC_{i}$, are based on the same sort of information process,
they are really two quite different objects. Diffusion centrality
is a gauge of a node's ability to send information, while the network
gossip measure tracks the reception of information by different nodes.
Indeed, the reason that Theorem \ref{prop:cov} is only stated for
the sum rather than any particular individual $j$'s network gossip
measure is that for small $T$ it is possible that some nodes have
not even heard about other nodes, and moreover they might be biased
towards their local neighborhoods.%
\footnote{ One might conjecture that more central nodes would be better ``listeners'':
for instance, having more accurate rankings than less central listeners
after a small number of periods. Although this might happen in some
networks, and for many comparisons, it is not guaranteed. None of
the centrality measures considered here ensure that a given node,
even the most central node, is positioned in a way to ``listen''
uniformly better than all other less central nodes. Typically, even
a most central node might be farther than some less central node from
some other important nodes. This can lead a less central node to hear
some things before even the most central node, and thus to have a
clearer ranking of at least some of the network before the most central
node. Thus, for small $T$, the $\sum$ is important in Theorem \ref{prop:cov}. %
} 

Next, we show that if individuals exchange gossip over extended periods
of time, every individual in the network is eventually able to \emph{perfectly}
rank others' centralities.

\begin{theorem} \label{prop:rank} If $p\geq1/\lambda_{1}$, then
as $T\rightarrow\infty$ every individual $j$'s ranking of others
under $NG({\bf g};p,T)_{j}$ will be according to the ranking of diffusion
centrality, $DC({\bf g};p,T)$, and hence according to eigenvector
centrality, $v^{(1)}$. \end{theorem}

The intuition is that individuals hear (exponentially) more often
about those who are more diffusion/eigenvector central, as the number
of rounds of communication tends to infinity. As such, in the limit,
they assess the rankings according to diffusion/eigenvector centrality
correctly. The result implies that with very little computational
ability beyond remembering counts and adding to them, agents come
to learn arbitrarily accurately complex measures of others' centralities,
even for people with whom they do not associate.

More sophisticated strategies in which individuals try to infer network
topology, could accelerate learning. Nonetheless, this result holds
even in a minimal environment wherein individuals do not know the
structure of the network and do not tag anything but the topic of
conversation (``Arun has a new car'').

The restriction to $p\geq1/\lambda_{1}$ is important. For example,
as $p$ tends to 0, then individuals hear with vanishing frequency
about others in the network, and network distance between people can
matter in determining whom they think is the most important.


\


\section{Data}

\label{sec:data}

To investigate the theory presented above, we examine new data, coupled
with detailed network data gathered from villages in rural Karnataka
(India). The network data consist of network information combined with ``gossip''
data for 35 villages.

To collect the network data (described in more details in \citep*{banerjeecdj2013},
and publicly available at \url{http://economics.mit.edu/faculty/eduflo/social}),
we surveyed adults regarding with whom they interact.%
\footnote{We have network data from 89.14\% of the 16,476 households based on
interviews with 65\% of all adult individuals aged 18-55.%
} We have data concerning 12 types of interactions for a given survey
respondent: (1) whose houses he or she visits, (2) who visit his or
her house, (3) his or her relatives in the village, (4) non-relatives
who socialize with him or her, (5) who gives him or her medical advice,
(6) from whom he or she borrows money, (7) to whom he or she lends
money, (8) from whom he or she borrows material goods (e.g., kerosene,
rice), (9) to whom he or she lends material goods, (10) from whom
he or she gets advice, (11) to whom he or she gives advice, (12) with
whom he or she goes to pray (e.g., at a temple, church or mosque).
Using these data, we construct one network for each village, at the
household level where a link exists between households if any member
of any household is linked to any other member of any other household
in at least one of the 12 ways.%
\footnote{Individuals can communicate if they interact in any of the 12 ways,
so this is the network of potential communications, and using this
network avoids the selection bias associated with data-mining to
find the most predictive subnetworks.%
} The resulting objects are undirected, unweighted networks at the
household level.


To collect the gossip data, we later asked the adults the following
two additional questions:


\begin{itemize}
\item[(Loan)]  \emph{If we want to spread information about a new loan product to everyone in your village, to whom do you suggest we speak?}

\

\item[(Event)] \emph{If we want to spread information to everyone in the village about tickets to a music event, drama, or fair that we would like to organize in your village, to whom should we speak?}
\end{itemize}




\begin{table}[!h]
\centering
\caption{Summary Statistics\label{tab:summary}}
\input{table0_v3.tex}
\begin{tablenotes}
Notes: for the variables nominated someone for loan (event) and was nominated for loan (event) we present the cross-village standard deviation.
\end{tablenotes}

\end{table}


\

Table \ref{tab:summary} provides some summary statistics for our
data. The networks are sparse: the average number of households in
a village is 196 with a standard deviation of 61.7, while the average
degree is 17.7 with a standard deviation of 9.8.

We see that only 5\% of households were named in response to the Loan
question (and 4\% for the Event question) with a cross-village standard
deviation of 3\%. Thus there is a substantial concordance in who is
named as a good initiator of diffusion within a village. In fact,
conditional on being nominated, a household was nominated nine times
on average.%
\footnote{We work at the household level, in keeping with \citet{banerjeecdj2013}
who used households as network nodes; a household receives a nomination
if any of its members are nominated.%
} This is perhaps a first indication that the answers may be meaningful.

The fact that less than half of the households were willing to name
someone, is itself intriguing. Perhaps people are unwilling to offer
an opinion when they are unsure of the answer%
\footnote{See \citet{alatas2012network} for a model that builds on this idea.%
} or possibly were afraid of offending someone, given that they were
asked to name just one person.

We label as ``leaders'' self-help group leaders, shopkeepers, teachers,
etc.: 13\% of households fall into this category. We use the term
as it was defined by the microfinance organization Bharatha Swamukti
Samsthe (BSS) as part of their strategy for identifying people to
initiate diffusion for their product. BSS approached such social leaders
because they were a priori likely to be important in the social learning
process and thereby would contribute to more diffusion of microfinance.
In our earlier work, \citet{banerjeecdj2013}, we show that there
is considerable variation in the centrality of these ``leaders''
in a network sense, and that this variation predicts the eventual
take up of microfinance.

\

\section{Empirical Analysis}
\label{sec:results}


Our theoretical results suggest that people can learn others' diffusion
or eigenvector centralities simply by tracking news they hear through
the network. Thus, they should be able to name central individuals
when asked whom to use as a ``seed'' for diffusion. If this is the
case, such direct questions can easily be added to standard survey
modules to identify central individuals without obtaining detailed
network data.


\subsection{Descriptive Evidence}

Figure \ref{fig:graph} shows a village network where we highlight
both the nominees and the village leaders used by BSS as seeds for
microfinance information, and thus the best guess of this organization
of the most highly central people.%
\footnote{This is not a geographic representation of nodes but, rather, a representation
using a simple algorithm to visually represent the sub-community structure
of the network.%
} We see in the figure that ``leaders'' include central households
but also some peripheral households. However, nominees appear to be
more central and are rarely peripheral. Additionally, nodes that are
both leaders and nominated are highly central.


\begin{figure}[!h]
\begin{center}
	\subfloat[Village network with leaders flagged]{
	\includegraphics[trim = 150mm 0mm 0mm 0mm, scale=0.08]{A54_core_dot-BLUE-Leaders.pdf}
	}
	\subfloat[Village network with nominees flagged]{
	\includegraphics[trim = 0mm 0mm -150mm 0mm, scale=0.08]{A54_core_dot-RED-Nominees.pdf}
	}
	
		\subfloat[Village network with nominees/leaders flagged]{
	\includegraphics[trim = 0mm 0mm 0mm 0mm, scale=0.08]{A54_core_dot-PURPLE.pdf}
	}
	\end{center}
		\caption{A village network with nominees (red), leaders (blue) and those who fulfill both categories (purple) flagged. \label{fig:graph}}
\end{figure}


Let us examine the relative network position of nominees in detail.
Since the relevant number of periods to compute diffusion centrality
is in principle application-dependent, we start with eigenvector centrality,
which is a limit as $T\rightarrow\infty$ of diffusion centrality
for large enough $p$ (above the inverse of the first eigenvalue).
We return to compare what happens with other $p$ and $T$, below.


\begin{figure}[!h]
\begin{center}
\includegraphics[trim = 2.5mm 4.85mm 2.5mm 2.5mm, clip = true, scale = 0.9]{predictCentrality}
\end{center}
\caption{The probability that a randomly chosen node with a given classification (whether or not it is nominated under the event question and whether or not it has a village leader) is in the top decile of the  eigenvector centrality distribution. 95\% confidence intervals are displayed. \label{fig:predictCentrality}}
\end{figure}


Figure \ref{fig:predictCentrality} builds on the theme presented
in Figure \ref{fig:graph}. Examining the likelihood that a nominated
household is highly central, we find that 47\% of households that
are both nominated and have a leader are within the top 10\% of the
eigenvector centrality distribution. Furthermore, 23\% of the households
that are nominated but are not leaders are in the top decile of the
centrality distribution.


This contrasts with households that are not nominated, irrespective
of whether they have a leader. Only 16\% of households that are not
nominated but have a leader, and only 7\% of households that are not
nominated and have no leader, are in the top decile of the eigenvector
centrality distribution.%
\footnote{The difference between the 23\% of households that are in the top
decile given that they are nominated but not leaders and the 16\%
in the top decile given that they are not nominated but are leaders
is significant with a $p$-value of 0.00 under a Welch test.%
} Another way to see this is that the average percentile in the
distribution of eigenvector centrality for those nominated for the
loan question is 0.71 (and 0.7 for event), while it is 0.62 for the
traditional leaders.


\begin{figure}[!h]
\begin{center}
	\subfloat[Loan Question]{
	\includegraphics[trim = 70mm 15mm 0mm 0mm, scale=0.25]{figure3.png}
	}
	\subfloat[Event Question]{
	\includegraphics[trim = 0mm 15mm 0mm 0mm, scale=0.25]{figure4.png}
	}
	\end{center}
		\caption{The average number of nominations per household vs. the quintile of the households' eigenvector centralities. \label{fig:pctilenominee}}
\end{figure}


Not only are nominated nodes more central in the network, but more
central nodes also receive more nominations, as predicted by the theory.
Figure \ref{fig:pctilenominee} shows that households with higher
levels of eigenvector centrality receive more nominations on average
than households of lower centrality, by a factor of about four when
comparing the highest quintile to the lowest.



Figure \ref{fig:neighborhood} presents the distribution of nominations
as a function of the network distance from a given household. If information
did not travel well through the social network, we might imagine that
individuals would only nominate households to whom they are directly
connected. Panel A of Figure \ref{fig:neighborhood} shows that fewer
than 20\% of individuals nominate someone within their direct neighborhood.
At the same time, over 27\% of nominations come from a network distance
of at least three or more. Taken together, this suggests that information
about centrality does indeed travel through the network.




From Panel A of Figure \ref{fig:neighborhood}, we also see that,
while people do nominate individuals in households who are closer
to them than the typical household in the village, respondents generally
name people outside of their immediate neighborhoods and sometimes
quite far. Moreover, it is important to note that highly central individuals
are generally closer to people than the typical household, so, if
they did nominate the most central people, this is what we should
expect to find.



It is plausible that individuals may not have good information about
who is central in parts of the network that are far from them. However,
in Panel B of Figure \ref{fig:neighborhood} we see that the average
eigenvector centrality percentile of those named at distance 1 is
the same as at distance 2 or distance 3 or more. This suggests that
individuals have reasonable and comparably accurate information about
central individuals in the community who are immediate neighbors or
at greater distance from them.

\begin{figure}[!h]
\begin{center}
	\subfloat[Share of nominees in specified neighborhood]{
	\includegraphics[trim = 80mm 12mm 0mm 0mm, scale=0.24]{figure2.png}
	}
	\subfloat[Average eigenvector centrality percentile of nominees in specified neighborhood]{
	\includegraphics[trim = 0mm 12mm 0mm 0mm, scale=0.24]{figure1.png}
	}
	\end{center}
		\caption{Distribution of centralities of nominees\label{fig:neighborhood}}
\end{figure}






\subsection{Regression Analysis}\label{sec:prediction}

Motivated by this evidence, we present a more systematic analysis
of the correlates of nominations, using a discrete choice framework
for the decision to nominate someone.

Our theory suggests that if people choose whom to nominate by picking
someone whom they hear about most frequently, then diffusion centrality
should be a leading predictor of nominations. While the aforementioned
results are consistent with this prediction, there are several plausible
alternative interpretations. For example, individuals may nominate
the person with the most friends, and people with many friends tend
to be more diffusion central than those with fewer friends (i.e.,
diffusion centrality with $T=1$ and $T>1$ can be positively correlated).
Alternatively, it may be that people simply nominate ``leaders''
within their village, or people who are central geographically, and
these also correlate with diffusion/eigenvector centrality. There
are indeed a priori reasons to think that leadership status and geography
may be good predictors of network centrality, since, as noted in \citet{banerjeecdj2013},
the microfinance organization selected ``leaders'' precisely because
they believed these people would be informationally central. Similarly,
previous research has shown that geographic proximity increases the
probability of link formation \citep{fafchampsg2007b,ambrusms2012,chandrasekharl2014}
and therefore one might expect geographic data to be a useful predictor
of centrality. In addition to leadership data we have detailed GPS
coordinates for every household in each village. We include this in
our analysis below.%
\footnote{To operationalize geographic centrality, we use two measures. The
first uses the center of mass. We compute the center of mass and then
compute the geographic distance for each agent $i$ from the center
of mass. Centrality is the inverse of this distance, which we normalize
by the standard deviation of this measure by village. The second uses
the geographic data to construct an adjacency matrix. We denote the
$ij$ entry of this matrix to be $\frac{1}{d(i,j)}$ where $d(\cdot,\cdot)$
is the geographic distance. Given this weighted graph, we compute
the eigenvector centrality measure associated with this network. Results
are robust to either definition.%
}

Of course, the correlations below are not a ``test'' that the causal
mechanism is indeed gossip, as in our model, but they do rule
out that our diffusion centrality measure simply picks out degree
centrality, geography or traditional leadership.

To operationalize our analysis using diffusion centrality, we need
to first identify $p$ and $T$. We use the average of the transmission
probability parameters estimated in \citet{banerjeecdj2013}, which
studies the diffusion of information about a loan, and finds $p=0.2$.
We set $T=3$, since the average distance between nodes in our network
is 2.7 and thus 3 represents the distance to which information travels
before it begins to echo backwards. In what follows, we use $DC(0.2,3)$
when we refer to diffusion centrality.

We estimate a discrete choice model of the decision to nominate an
individual. Note that we have large choice sets as there are $n-1$
possible nominees and $n$ nominators per village network. We model
agent $i$ as receiving utility $u_{i}(j)$ for nominating individual
$j$: 
\[
u_{i}(j)=\alpha+\beta'x_{j}+\gamma'z_{j}+\mu_{v}+\epsilon_{ij,v},
\]
where $x_{j}$ is a vector of network centralities for $j$ (eigenvector
centrality, $DC(0.2,3)$, and degree centrality), $z_{j}$ is a vector
of demographic characteristics (e.g., leadership status, geographic
position and caste controls), $\mu_{v}$ is a village fixed effect,
and $\epsilon_{iv,j}$ is a Type-I extreme value distributed disturbance.
For convenience given the large choice sets, we estimate the conditional
logit model by an equivalent Poisson regression, where the outcome
is the expected number of times an alternative is selected \citep{palmgren1981fisher,baker1994multinomial,lang1996comparison,guimaraes2003tractable}.

Table \ref{tab:poisson} presents our estimates of $\beta$ and $\gamma$. 
\begin{table}[!h]
\centering
\caption{Factors predicting nominations}\label{tab:poisson}
\scalebox{0.8}{\begin{threeparttable}
\input{tablePoisson.tex}
\begin{tablenotes}
Notes: The table reports estimate of a Poisson regression where the outcome variable is the expected number of nominations under the loan question. Degree centrality, eigenvector centrality and $DC(0.2,3)$ are normalized by within-village standard deviation. Standard errors (clustered at the village level) are reported in parentheses.  *** $p<0.01$, ** $p<0.05$, * $ p < 0.1$.
\end{tablenotes}
\end{threeparttable}}
\end{table}
First we show that $DC(0.2,3)$ is a significant driver of an individual
nominating another (column 1). A one standard deviation increase in
eigenvector centrality is associated with a 0.634 log-point increase
in the number of others nominating a household (statistically significant
at the 1\% level). In column 2 we see that this is robust to controlling
for leadership status, geographic centrality of households, as well
as village and caste fixed effects: a one standard deviation increase
in diffusion centrality is associated with a 0.616 log-point increase
in the number of others nominating the household (significant at the
1\% level). Leadership status does affect the number of nominations
as well, as we saw in the descriptive evidence, but the point estimate
of the diffusion centrality coefficient hardly changes.

In columns 3-5 we add eigenvector and degree centrality as points
of comparison. It seems that it is indeed diffusion centrality that
best predicts nominations. A one standard deviation in $DC(0.2,3)$
corresponds to a 0.639 log-point increase in the number of nominations
(statistically significant at the 5\% level) as compared to -0.005
log-points when looking at eigenvector centrality (not statistically
significant, column 3). Similarly, including both $DC(0.2,3)$ and
degree centrality leaves the coefficient on $DC(0.2,3)$ mostly unchanged,
a 0.749 log-point increase in the number of nominations associated
with a one standard deviation increase in centrality, whereas there
is no statistically significant association with degree centrality
and the point estimate is considerably smaller (-0.117, column 4).
However, parameter estimates are noisy and one cannot reject the hypothesis
that the coefficients on $DC(0.2,3)$ and eigenvector centrality as
well as $DC(0.2,3)$ and degree are statistically the same, despite
the difference in the point estimates. The $p$-values of a test of
equality of coefficients are 0.248 and 0.279 in columns 3 and 4, respectively
(see the last row of the table). Further, we include all three centrality
measures in column 5 and are unable to reject that any individual
coefficient is statistically different from zero, although they are
jointly significant with a $p$-value of 0.00). The point estimate
of $DC(0.2,3)$ remains similar to those in column 4, and both degree
and eigenvector centrality have negative point estimates. However,
due to the colinearity of the three centrality variables, standard
errors are more than twice as large than in the previous columns.
Columns 6-8 repeat the exercises of columns 3-5, now including leadership
status and geographic centrality as extra control variables. Additionally,
we add village and household caste fixed effects. As before we find that
$DC(0.2,3)$ enters significantly and with similar effect sizes, unless
all three centralities are included, where the estimates become noisy.
Moreover, in our pairwise comparisons neither degree nor eigenvector
centrality coefficients are large and statistically significant drivers
of the number of nominations.

Our results provide suggestive evidence that a key driver of
the nomination decision involves diffusion centrality with $T>1$
although, given the high degree of correlation of these metrics in
our sample, we cannot statistically reject that all centrality variables
matter equally. The point estimates, however, point towards the diffusion
centrality as the most robust factor. Overall, it is clear that individuals
are able to accurately name highly central individuals, well beyond
using other status variables.

\


\section{Concluding Remarks}\label{sec:conclusion}

Our model illustrates that it should be easy for even very myopic
and non-Bayesian agents, simply by counting, to have an idea as to
who is central in their community (according to fairly complex definitions).
Motivated by this, we asked villagers to identify central individuals
in their village. They do not simply name locally central individuals
(the most central among those they know), but actually name ones that
are \emph{globally} central within the village. This suggests that
individuals may use simple protocols to learn valuable things about
the complex systems within which they are embedded.

Our findings have important policy implications, since such nomination
data are easily collected and therefore can be used in a variety of
contexts, either on its own, or combined with other easily collected
data, to identify who would be a good seed for an information. For
instance, if a household is both a nominee and a leader, it has a
47\% likelihood of being in the top 10\% of the centrality distribution.

It is also worth commenting that our work focuses on the network-based
mechanics of communication. In practice, considerations beyond simple
network position may determine who the ``best'' person is to spread
information, as other characteristics may affect the quality and impact
of communication. An avenue for further research is to investigate
whether villagers take such characteristics into account and thus
may nominate individuals who are even more successful at diffusing
information than the most central individual in the network. Beyond
these, the work presented here opens a rich agenda for further research,
as one can explore which other aspects of agents' social environments
can be learned in simple ways.




\bibliographystyle{ecta}
\bibliography{networks}

\newpage

\appendix


\section{Proofs}

We prove all of the statements for the case of weighted and directed networks.


Let $v^{\left(L,k\right)}$ indicate $k$-th left-hand side eigenvector of ${\bf g}$ and similarly let $v^{\left(R,k\right)}$
indicate ${\bf g}$'s $k$-th right-hand side eigenvector.  In the case of undirected networks, $v^{\left(L,k\right)}=v^{\left(R,k\right)}$.
In the case of directed networks, eigenvector $v^{\left(1\right)}$ in the main body
corresponds to $v^{\left(R,1\right)}$.

The following lemma is used in proofs of the theorems.


\begin{lemma}
\label{diag}
Consider a positive and diagonalizable $\g$.  Then $\g$ has a unique largest eigenvalue.
Moreover, letting $\widetilde{{\bf g}}={\bf g}/\lambda_{1}$,
\[
[\widetilde{ g}^T]_{ij}\rightarrow_T v_{i}^{\left(R,1\right)}v_{j}^{\left(L,1\right)}.
\]
\end{lemma}

\begin{proof}[{\bf Proof of Lemma \ref{diag}}]
The uniqueness of the largest eigenvalue follows from the Perron-Frobenius Theorem (given that $g$ is positive).
By diagonalizability we can write
${\bf g}$ as
\[
{\bf g}={\bf V}\Lambda {\bf V}^{-1}
\]
where $\Lambda$ is the matrix with eigenvalues on the diagonal (ordered from 1 to $n$ in order of magnitude) and ${\bf V}$ is the matrix with columns equal to the right-hand eigenvectors, and ${\bf V}^{-1}$ is not only ${\bf V}$'s inverse, but is also the matrix with rows equal to the left-hand eigenvectors.  By normalizing $\widetilde{{\bf g}}={\bf g}/\lambda_{1}$, it follows that $\widetilde{{\bf g}}={\bf V}\widetilde{\Lambda}{\bf V}^{-1}$,
where $\widetilde{\Lambda}$ is the diagonal matrix such that
$\widetilde{\Lambda}={\rm diag}\left\{ 1,\widetilde{\lambda}_{2},...,\widetilde{\lambda}_{n}\right\} $, and $\widetilde{\lambda}_{k} = \frac{{\lambda}_{k}}{\lambda_{1}}$.
Since the largest eigenvalue of ${\bf g}$ is unique, it also follows that $0\leq\left|\widetilde{\lambda}_{k}\right|<1$ for $k>1$.

It helps to write the $ik$-th entry of ${\bf V}$ as $v_{i}^{\left(R,k\right)}$, and similarly, the
$kj$-th entry of ${\bf V^{-1}}$ is written as $v_{j}^{\left(L,k\right)}$.
Therefore, it is straightforward to check that
\[
\widetilde{{\bf g}}^{T}_{ij}
=\sum_{k=1}^n v_{i}^{\left(R,k\right)}v_{j}^{\left(L,k\right)}\widetilde{\lambda}_{k}^{T}.
\]
Separating terms,
\[
\widetilde{{\bf g}}^{T}_{ij}
=v_{i}^{\left(R,1\right)}v_{j}^{\left(L,1\right)} + \sum_{k=2}^n v_{i}^{\left(R,k\right)}v_{j}^{\left(L,k\right)}\widetilde{\lambda}_{k}^{T}.
\]
Thus,
given that  $\widetilde{\lambda_k}^T\rightarrow 0$ for $k\geq 2$, it follows that
\[
\widetilde{{\bf g}}^{T}_{ij} \rightarrow_{T\rightarrow \infty}
v_{i}^{\left(R,1\right)}v_{j}^{\left(L,1\right)} ,
\]
as claimed.
\end{proof}

\bigskip

\begin{proof}[{\bf Proof of Theorem \ref{DC}}]
We show the second statement as the others follow directly.

First, note that in any neighborhood of any nonnegative matrix $\g$, there exists
a {positive} and diagonalizable matrix $\g'$.
Next, consider any nonnegative $\g$.  If the statement holds for
any arbitrarily close positive and diagonalizable $\g'$, then since $\frac{{DC}\left({\bf g};p,T\right)}{\sum_{t=1}^T \left( p \lambda_1\right)^{t}}$ is a continuous function (in a neighborhood of a nonnegative and strongly connected $\g$)
as is the first eigenvector, the statement also holds at $\g$.
Thus, it is enough to prove the result for a positive and diagonalizable $\g$,
as in what follows.

In fact, we show the following strengthening of the statement for a positive and diagonalizable $\g$.
\begin{itemize}
		\item The `tail terms' approach eigenvector centrality: $$({\bf g}/\lambda_1)^{t}\cdot{\bf 1}\rightarrow{v}^{\left(R,1\right)} \mbox{ as } t\rightarrow \infty.$$

		\item  If $p> \lambda_1^{-1}$, then
$$\lim_{T\rightarrow\infty}\frac{{DC}\left({\bf g};p,T\right)}{\sum_{t=1}^T \left( p \lambda_1\right)^{t}}= \lim_{T\rightarrow\infty} \frac{{DC}\left(g;p,T\right)}{\frac{ p \lambda_1-(p \lambda_1)^{T+1}}{1-(p \lambda_1)}}= {v}^{\left(R,1\right)}.$$

\item If $p = \lambda_1^{-1}$, then

$$\lim_{T\rightarrow\infty}\frac{1}{T}{DC}\left({\bf g};\lambda_{1}^{-1},T\right) = {v}^{\left(R,1\right)}.$$
\end{itemize}

\

By diagonalizability we write
\[
{\bf g}={\bf V}\Lambda {\bf V}^{-1},
\]
and normalizing $\widetilde{{\bf g}}={\bf g}/\lambda_{1}$ it follows that $\widetilde{{\bf g}}={\bf V}\widetilde{\Lambda}{\bf V}^{-1}$.
Normalize the eigenvectors to lie in $\ell_{1}$,
so the entries in each column of ${\bf V}^{-1}$ and each row of ${\bf V}$ sum to 1.
Then, applying Lemma \ref{diag}, it follows that $\widetilde{{\bf g}}^{T}\cdot{\bf 1}$ is
such that
\[
\widetilde{{\bf g}}^{T}\cdot{\bf 1}\rightarrow{ v}^{\left(R,1\right)}.
\]
This completes the proof of the first statement.

Next, we turn to the sum $\sum_{t=1}^{\infty}\widetilde{{\bf g}}^{t}\cdot{\bf 1}$ and show the second statement for the case where $p=1/\lambda_1$. It is sufficient to show
\[
\lim_{T\rightarrow\infty}\left\Vert \frac{DC\left(\g;\lambda_{1}^{-1},T\right)}{T}-{v}^{(R,1)}\right\Vert =0.
\]
First, note that as with our calculations above,
\[
DC_{i}\left(\g;\lambda_{1}^{-1},T\right) =\sum_j \sum_{t=1}^T \sum_k  v_i^{(R,k)} v_j^{(L,k)} \widetilde{\lambda}_{k}^{t}
\]
Thus,
\begin{eqnarray*}
\left|\frac{DC_{i}\left(\g;\lambda_{1}^{-1},T\right)}{T}-v_{i}^{(R,1)}\right| & = &
\left|\frac{ \sum_j \sum_{t=1}^T \sum_{k=1}^n  v_i^{(R,k)} v_j^{(L,k)} \widetilde{\lambda}_{k}^{t}}{T} -v_{i}^{(R,1)} \right| =  \\
& = & \left|\frac{1}{T} \sum_j \sum_{t=1}^T \sum_{k= 2}^n  v_i^{(R,k)} v_j^{(L,k)} \widetilde{\lambda}_{k}^{t} \right|\leq\frac{1}{T}\sum_{t=1}^{T}\sum_{k=2}^{n}1\cdot\underbrace{\left|\sum_{j=1}^{n}v_{j}^{(L,k)}\right|}_{\leq1}
\cdot\left|\widetilde{\lambda}_{k}^{t}\right|\\
 & \leq & \frac{n}{T}\sum_{t=1}^{T}\left|\widetilde{\lambda}_{2}^{t}\right|=\frac{n}{T}\frac{\left|\widetilde{\lambda}_{2}\right|}{1-\left|\widetilde{\lambda}_{2}\right|}\left(1-\left|\widetilde{\lambda}_{2}\right|^{T}\right)\rightarrow0.
\end{eqnarray*}
Since the length of the vector (which is $n$) is unchanging in $T$, pointwise
convergence implies convergence in norm, proving the result.

The final piece repeats the argument for $p>1/\lambda_1$, but now uses the definition $\widetilde{{\bf g}} = (p{\bf g})$. Then we have $\widetilde{\Lambda} = {\rm diag}\left\{\widetilde{\lambda}_1,...,\widetilde{\lambda}_n\right\}$ with $p\lambda_k = \widetilde{\lambda}_k$.  We show
\[
\lim_{T\rightarrow\infty}\left\Vert \frac{DC\left(\g;p,T\right)}{\sum_{t=1}^{T}\left(p\lambda_{1}\right)^{t}}-{v}^{(R,1)}\right\Vert =0.
\]
By similar derivations as above,
\begin{eqnarray*}
\left|\frac{DC_{i}\left(\g;\lambda_{1}^{-1},T\right)}{\sum_{t=1}^{T}\widetilde{\lambda}_{1}^{t}}-v_{i}^{(R,1)}\right| & = &
\left|\frac{ \sum_j \sum_{t=1}^T \sum_{k=1}^n  v_i^{(R,k)} v_j^{(L,k)} \widetilde{\lambda}_{k}^{t}}{\sum_{t=1}^{T}\widetilde{\lambda}_{1}^{t}} -v_{i}^{(R,1)} \right| =  \\
& = & \left|\frac{1}{\sum_{t=1}^{T}\widetilde{\lambda}_{1}^{t}} \sum_j \sum_{t=1}^T \sum_{k= 2}^n  v_i^{(R,k)} v_j^{(L,k)} \widetilde{\lambda}_{k}^{t} \right|\\
& \leq &\frac{1}{\sum_{t=1}^{T}\widetilde{\lambda}_{1}^{t}}\sum_{t=1}^{T}\sum_{k=2}^{n}1\cdot
\left|\sum_{j=1}^{n}v_{j}^{(L,k)}\right|
\cdot\left|\widetilde{\lambda}_{k}^{t}\right|\\
 & \leq & \frac{n}{\sum_{t=1}^{T}\widetilde{\lambda}_{1}^{t}}\sum_{t=1}^{T}\left|\widetilde{\lambda}_{2}^{t}\right|.
\end{eqnarray*}
Note that this last expression converges to 0 since $\widetilde{\lambda}_{1}>1$, and
$\widetilde{\lambda}_{1}>\widetilde{\lambda}_{2}$.\footnote{\label{fn:domination}Note that it is important
that $p\geq 1/\lambda_1$ for this claim, since if $p < 1/ \lambda_1$, then $p \lambda_1 < 1$. In that case, observe that
$$ \frac{\sum_{t=1}^{T}\left|\tilde{\lambda}_{2}\right|^{t}}{\sum_{t=1}^{T}\tilde{\lambda}_{1}^{t}} = \frac{\widetilde{\lambda}_2}{\widetilde{\lambda}_1} \cdot \frac{1-\tilde{\lambda_1}}{1-\tilde{\lambda_2}}$$ by the properties of a geometric sum, which is of constant order.  Thus, higher order terms ($\widetilde{\lambda}_2$, etc.) persistently matter and are not dominated relative to $\sum_t^T \widetilde{\lambda}_1^t$.}
which completes the argument.
\end{proof}

\


\begin{proof}[{\bf Proof of Theorem \ref{prop:cov}}]
Recall that
$
\bfH= \sum_{t=1}^{T}\left(p{\bf g}\right)^{t}
$ and
$
DC =
\left(\sum_{t=1}^{T}\left(p{\bf g}\right)^{t}\right)\cdot{\bf 1}
$
and so
$$
DC_i = \sum_{j}H_{ij}.
$$

Additionally,
$$\cov (DC,H_{\cdot,j}) =
\sum_i  \left(DC_i- \sum_k \frac{DC_k}{n}\right)\left(H_{ij} - \sum_k \frac{H_{kj}}{n}\right).
$$
Thus
$$\sum_j\cov (DC,H_{\cdot,j}) =
\sum_i  \left(DC_i- \sum_k \frac{DC_k}{n}\right)\left(\sum_j H_{ij} - \sum_k \frac{\sum_j H_{kj}}{n}\right),
$$
implying
$$\sum_j\cov (DC,H_{\cdot,j}) =
\sum_i  \left(DC_i- \sum_k \frac{DC_k}{n}\right)\left(DC_i- \sum_k \frac{DC_k}{n}\right)
=\var(DC),
$$
which completes the proof.
\end{proof}

\


\begin{proof}[{\bf Proof of Theorem \ref{prop:rank}}]
Again, we prove the result for a positive diagonalizable $\g$, noting that it then holds for any (nonnegative) $\g$.

Again, let $\g$ be written as
\[
\g={\bf V}\Lambda {\bf V}^{-1}.
\]
Also, let $\tilde{\lambda}_{k}=p\lambda_{k}$.
It then follows that we can write
\[
{\bf H}=\sum_{t=1}^{T}\left(p{\bf g}\right)^{t} =\sum_{t=1}^{T}\left(\sum_{k=1}^n v_{i}^{\left(R,k\right)}v_{j}^{\left(L,k\right)}\widetilde{\lambda}_{k}^{t}\right).
\]
By the ordering of the eigenvalues from largest to smallest in magnitude,
\begin{eqnarray*}
{\bf H}_{\cdot,j} & = & \sum_{t=1}^{T}\left[{ v}^{(R,1)}v_{j}^{(L,1)}\tilde{\lambda}_{1}^{t}+{ v}^{(R,2)}v_{j}^{(L,2)}\tilde{\lambda}_{2}^{t}+O\left(\left|\tilde{\lambda}_{2}\right|^{t}\right)\right]\\
 & = & \sum_{t=1}^{T}\left[{ v}^{(R,1)}v_{j}^{(L,1)}\tilde{\lambda}_{1}^{t}+O\left(\left|\tilde{\lambda}_{2}\right|^{t}\right)\right]\\
 & = & { v}^{(R,1)}v_{j}^{(L,1)}\sum_{t=1}^{T}\tilde{\lambda}_{1}^{t}+O\left(\sum_{t=1}^{T}\left|\tilde{\lambda}_{2}\right|^{t}\right).
\end{eqnarray*}
So, since the largest eigenvalue is unique, it follows that
\[
\frac{{\bf H}_{\cdot,j}}{\sum_{t=1}^{T}\tilde{\lambda}_{1}^{t}}={ v}^{(R,1)}v_{j}^{(L,1)}+O\left(\frac{\sum_{t=1}^{T}\left|\tilde{\lambda}_{2}\right|^{t}}{\sum_{t=1}^{T}\tilde{\lambda}_{1}^{t}}\right).
\]
Note that the last expression converges to 0 since $\widetilde{\lambda}_{1}>1$, and
$\widetilde{\lambda}_{1}>\widetilde{\lambda}_{2}$.
Thus,
\[
\frac{{\bf H}_{\cdot,j}}{\sum_{t=1}^{T}\tilde{\lambda}_{1}^{t}}\rightarrow { v}^{(R,1)}v_{j}^{(L,1)}
\]
for each $j$.
This completes the proof since each column of ${\bf H}$ is proportional to ${ v}^{(R,1)}$ in the limit, and thus has the correct ranking for large enough $T$.\footnote{The discussion in Footnote \ref{fn:domination} clarifies why $p > 1/\lambda_1$ is required for the argument.}
Note that the ranking is up to ties, as the ranking of tied entries may vary arbitrarily along the sequence.  That is, if
${ v}^{(R,1)}_{i}={ v}^{(R,1)}_{\ell}$, then the ranking that $j$ has over $i$ and $\ell$ could vary arbitrarily with $T$, but their rankings will be correct relative to any other entries with higher or lower eigenvector centralities.
\end{proof}






\end{document}


table0_v3.tex
{
\def\sym#1{\ifmmode^{#1}\else\(^{#1}\)\fi}
\begin{tabular}{l*{1}{cc}}
\hline\hline
                    &\multicolumn{1}{c}{}&            \\
                    &        mean&          sd\\
\hline
households per village & 196  &  61.70    \\
household degree              &       17.72&      (9.81)\\
clustering in a household's neighborhood & 0.29 & (0.16) \\
%household eigenvector centrality&        0.46&      (0.33)\\
%avg. neighbors eig  &        0.56&      (0.25)\\
%rumor centrality    &      118.76&     (63.09)\\
%avg. neighbors rum  &      136.75&     (47.94)\\
avg distance between nodes in a village    &  2.37     &  (0.33)       \\
fraction in the giant component  & 0.98    &  (0.01)       \\
%avg closeness between nodes in a village & 0.46 &    (0.08) \\
is a ``leader''              &        0.13&      (0.34)\\
nominated someone for loan &        0.48&      (0.16)\\
nominated someone for event&        0.38&      (0.16)\\
was nominated for loan  &        0.05&      (0.03)\\
was nominated for event&        0.04&      (0.02)\\
number of nominations received for loan&        0.45&      (3.91)\\
number of nominations received for event&        0.34&      (3.28)\\
%gps centrality      &     3656.41&  (16204.00)\\
%gps eigenvector centrality&        0.51&      (0.36)\\
%\hline
%Observations        &        6466&            \\
\hline\hline
\end{tabular}
}

tablePoisson.tex
\begin{tabular}{lccccccccc} \hline
  & (1) & (2) & (3) & (4) & (5) & (6) & (7) & (8) \\ \hline
   &  &  &  &  &  &  &  &  \\
 $DC(0.2,3)$ & 0.634*** & 0.616*** & 0.639** & 0.749* & 0.982 & 0.681* & 0.727* & 1.208 \\
   & (0.073) & (0.099) & (0.286) & (0.399) & (0.814) & (0.358) & (0.427) & (1.179) \\
 Eigenvector Centrality &  &  & -0.005 &  & -0.142 & -0.064 &  & -0.300 \\
   &  &  & (0.276) &  & (0.350) & (0.349) &  & (0.594) \\
   Degree Centrality &  &  &  & -0.117 & -0.208 &  & -0.113 & -0.295 \\
   &  &  &  & (0.405) & (0.535) &  & (0.428) & (0.662) \\
  Leader &  & 0.637**  &  &  &  & 0.636** & 0.640** & 0.640** \\
   &  & (0.298)  &  &  &  & (0.298) & (0.296) & (0.296) \\
  Geographic Centrality &  &  -0.305  &  &  &  & -0.303 & -0.309 & -0.308 \\
   &  &  (0.216) &  &  &  & (0.215) & (0.217) & (0.217) \\
   &  &  &  &  &  &  &  &  \\
  Observations & 6,466 & 5,733 & 6,466 & 6,466 & 6,466 & 5,733 & 5,733 & 5,733 \\
  Village and Caste FE & No & Yes & No & No & No & Yes & Yes & Yes \\ \hline
  $p-$value of $\beta_{DC(0.2,3)} = \beta_{\mbox{Eigenvector}}$  & & & 0.248 & & 0.324 & 0.288 & & 0.389 \\ 
    $p-$value of $\beta_{DC(0.2,3)} = \beta_{\mbox{Degree}}$   & & & & 0.279 & 0.373 & & 0.323 & 0.410 \\ \hline
\end{tabular}

bcdjgossip_Aug-11_2014.bbl
\begin{thebibliography}{24}
\newcommand{\enquote}[1]{``#1''}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi

\bibitem[\protect\citeauthoryear{Alatas, Banerjee, Chandrasekhar, Hanna, and
  Olken}{Alatas et~al.}{2014}]{alatas2012network}
\textsc{Alatas, V., A.~Banerjee, A.~G. Chandrasekhar, R.~Hanna, and B.~A.
  Olken} (2014): \enquote{Network structure and the aggregation of information:
  Theory and evidence from Indonesia,} \emph{NBER Working Paper}.

\bibitem[\protect\citeauthoryear{Ambrus, Mobius, and Szeidl}{Ambrus
  et~al.}{2014}]{ambrusms2012}
\textsc{Ambrus, A., M.~Mobius, and A.~Szeidl} (2014): \enquote{Consumption
  Risk-Sharing in Social Networks,} \emph{American Economic Review}, 104,
  149--82.

\bibitem[\protect\citeauthoryear{Baker}{Baker}{1994}]{baker1994multinomial}
\textsc{Baker, S.~G.} (1994): \enquote{The multinomial-Poisson transformation,}
  \emph{The Statistician}, 495--504.

\bibitem[\protect\citeauthoryear{Ballester, Calv{\'o}-Armengol, and
  Zenou}{Ballester et~al.}{2006}]{ballestercz2006}
\textsc{Ballester, C., A.~Calv{\'o}-Armengol, and Y.~Zenou} (2006):
  \enquote{{Who's who in networks, wanted: the key player},}
  \emph{Econometrica}, 74, 1403--1417.

\bibitem[\protect\citeauthoryear{Banerjee, Breza, Chandrasekhar, Duflo, and
  Jackson}{Banerjee et~al.}{2014}]{banerjeebcdj2014}
\textsc{Banerjee, A., E.~Breza, A.~Chandrasekhar, E.~Duflo, and M.~Jackson}
  (2014): \enquote{Come play with me: information diffusion about rival goods,}
  \emph{mimeo: MIT, Columbia, and Stanford}.

\bibitem[\protect\citeauthoryear{Banerjee, Chandrasekhar, Duflo, and
  Jackson}{Banerjee et~al.}{2013}]{banerjeecdj2013}
\textsc{Banerjee, A., A.~Chandrasekhar, E.~Duflo, and M.~Jackson} (2013):
  \enquote{Diffusion of Microfinance,} \emph{Science}, 341, DOI:
  10.1126/science.1236498, July 26 2013.

\bibitem[\protect\citeauthoryear{Benzi and Klymko}{Benzi and
  Klymko}{2014}]{benzik2014}
\textsc{Benzi, M. and C.~Klymko} (2014): \enquote{A matrix analysis of
  different centrality measures,} \emph{arXiv:1312.6722v3}.

\bibitem[\protect\citeauthoryear{Bloch, Demange, and Kranton}{Bloch
  et~al.}{2014}]{blochdk2014}
\textsc{Bloch, F., G.~Demange, and R.~Kranton} (2014): \enquote{Rumors and
  Social Networks,} \emph{Paris School of Economics, Working paper 2014 - 15}.

\bibitem[\protect\citeauthoryear{Borgatti}{Borgatti}{2005}]{borgatti2005}
\textsc{Borgatti, S.~P.} (2005): \enquote{Centrality and network flow,}
  \emph{Social Networks}, 27, 55 -- 71.

\bibitem[\protect\citeauthoryear{Chandrasekhar and Lewis}{Chandrasekhar and
  Lewis}{2014}]{chandrasekharl2014}
\textsc{Chandrasekhar, A. and R.~Lewis} (2014): \enquote{Econometrics of
  sampled networks,} Stanford working paper.

\bibitem[\protect\citeauthoryear{Dodds, Muhamad, and Watts}{Dodds
  et~al.}{2003}]{doddsmw2003}
\textsc{Dodds, P.~S., R.~Muhamad, and D.~J. Watts} (2003): \enquote{An
  Experimental Study of Search in Global Social Networks,} \emph{Science}, 301,
  827--829.

\bibitem[\protect\citeauthoryear{Fafchamps and Gubert}{Fafchamps and
  Gubert}{2007}]{fafchampsg2007b}
\textsc{Fafchamps, M. and F.~Gubert} (2007): \enquote{{The formation of risk
  sharing networks},} \emph{Journal of Development Economics}, 83, 326--350.

\bibitem[\protect\citeauthoryear{Golub and Jackson}{Golub and
  Jackson}{2010}]{golubj2010}
\textsc{Golub, B. and M.~Jackson} (2010): \enquote{{Naive Learning in Social
  Networks and the Wisdom of Crowds},} \emph{American Economic Journal:
  Microeconomics}, 2, 112--149.

\bibitem[\protect\citeauthoryear{Guimaraes, Figueirdo, and Woodward}{Guimaraes
  et~al.}{2003}]{guimaraes2003tractable}
\textsc{Guimaraes, P., O.~Figueirdo, and D.~Woodward} (2003): \enquote{A
  tractable approach to the firm location decision problem,} \emph{Review of
  Economics and Statistics}, 85, 201--204.

\bibitem[\protect\citeauthoryear{Jackson}{Jackson}{2008}]{jackson2008}
\textsc{Jackson, M.} (2008): \emph{Social and Economic Networks}, Princeton:
  Princeton University Press.

\bibitem[\protect\citeauthoryear{Jackson and Yariv}{Jackson and
  Yariv}{2011}]{jacksony2011}
\textsc{Jackson, M. and L.~Yariv} (2011): \enquote{Diffusion, strategic
  interaction, and social structure,} \emph{Handbook of Social Economics, San
  Diego: North Holland, edited by Benhabib, J. and Bisin, A. and Jackson, M.O.}

\bibitem[\protect\citeauthoryear{Katz and Lazarsfeld}{Katz and
  Lazarsfeld}{1955}]{katzl1955}
\textsc{Katz, E. and P.~Lazarsfeld} (1955): \emph{Personal influence: The part
  played by people in the flow of mass communication}, Free Press, Glencoe, IL.

\bibitem[\protect\citeauthoryear{Kempe, Kleinberg, and Tardos}{Kempe
  et~al.}{2003}]{kempekt2003}
\textsc{Kempe, D., J.~Kleinberg, and E.~Tardos} (2003): \enquote{Maximizing the
  Spread of Influence through a Social Network,} \emph{Proc. 9th Intl. Conf. on
  Knowledge Discovery and Data Mining}, 137 -- 146.

\bibitem[\protect\citeauthoryear{Kempe, Kleinberg, and Tardos}{Kempe
  et~al.}{2005}]{kempekt2005}
---\hspace{-.1pt}---\hspace{-.1pt}--- (2005): \enquote{Influential Nodes in a
  Diffusion Model for Social Networks,} \emph{In Proc. 32nd Intl. Colloq. on
  Automata, Languages and Programming}, 1127 -- 1138.

\bibitem[\protect\citeauthoryear{Lang}{Lang}{1996}]{lang1996comparison}
\textsc{Lang, J.~B.} (1996): \enquote{On the comparison of multinomial and
  Poisson log-linear models,} \emph{Journal of the Royal Statistical Society.
  Series B (Methodological)}, 253--266.

\bibitem[\protect\citeauthoryear{Lawyer}{Lawyer}{2014}]{lawyer2014}
\textsc{Lawyer, G.} (2014): \enquote{Understanding the spreading power of all
  nodes in a network: a continuous-time perspective,} \emph{arXiv:1405.6707v2}.

\bibitem[\protect\citeauthoryear{Milgram}{Milgram}{1967}]{milgram1967}
\textsc{Milgram, S.} (1967): \enquote{The small world problem,}
  \emph{Psychology Today}.

\bibitem[\protect\citeauthoryear{Palmgren}{Palmgren}{1981}]{palmgren1981fisher}
\textsc{Palmgren, J.} (1981): \enquote{The Fisher information matrix for log
  linear models arguing conditionally on observed explanatory variables,}
  \emph{Biometrika}, 563--566.

\bibitem[\protect\citeauthoryear{Rogers}{Rogers}{1995}]{rogers1995}
\textsc{Rogers, E.} (1995): \emph{Diffusion of Innovations}, Free Press.

\end{thebibliography}
