text:
function output = ge_cylinder(X,Y,radius,height,varargin)
% Reference page in help browser:
%
% link to html documentation
% show license statement
%

AuthorizedOptions = authoptions( mfilename );

%%%% Assign default parameter values, part of which will
%%%% be overwritten later on during the parsing of parameters:
         id = 'cylinder';
      idTag = 'id';
       name = 'ge_cylinder';
description = '';
    timeStamp = ' ';
timeSpanStart = ' ';
 timeSpanStop = ' ';
 visibility = 1;
  lineColor = 'ffffffff';
  polyColor = 'ffffffff';
  lineWidth = 1.0;
    snippet = ' ';
   divisions = 8;
 altitudeMode = 'relativeToGround';
    region = ' ';

parsepairs %script that parses Parameter/value pairs.

if( isempty( Y ) || isempty( X ) || isempty( radius ) || isempty( height ))
    error('empty coordinates passed to ge_cylinder(...).');
end

if ~(isequal(altitudeMode,'clampToGround')||...
   isequal(altitudeMode,'relativeToGround')||...
   isequal(altitudeMode,'absolute'))

    error(['Variable ',39,'altitudeMode',39, ' should be one of ' ,39,'clampToGround',39,', ',10,39,'relativeToGround',39,', or ',39,'absolute',39,'.' ])

end
if region == ' '
	region_chars = '';
else
	region_chars = [ region, 10 ];
end

id_chars = [ idTag '="' id '"' ];
poly_id_chars = [ idTag '="poly_' id '"' ];
name_chars = [ '<name>',10, name,10, '</name>',10 ];
description_chars = [ '<description>',10,'<![CDATA[' description ']]>',10,'</description>',10 ];
visibility_chars = [ '<visibility>',10,int2str(visibility),10,'</visibility>',10 ];
lineColor_chars = [ '<color>',10, lineColor([1,2,7,8,5,6,3,4]),10, '</color>',10 ];
polyColor_chars = [ '<color>',10, polyColor([1,2,7,8,5,6,3,4]) ,10,'</color>',10 ];
lineWidth_chars= [ '<width>',10, num2str(lineWidth, '%.2f') ,10,'</width>',10 ];
altitudeMode_chars = [ '<altitudeMode>',10, altitudeMode,10, '</altitudeMode>',10 ];

if snippet == ' '
    snippet_chars = '';
else
    snippet_chars = [ '<Snippet>' snippet '</Snippet>',10 ];
end

if timeStamp == ' '
    timeStamp_chars = '';
else
    timeStamp_chars = [ '<TimeStamp><when>' timeStamp '</when></TimeStamp>',10 ];
end

if timeSpanStart == ' '
    timeSpan_chars = '';
else
    if timeSpanStop == ' '
        timeSpan_chars = [ '<TimeSpan><begin>' timeSpanStart '</begin></TimeSpan>',10 ];
    else
        timeSpan_chars = [ '<TimeSpan><begin>' timeSpanStart '</begin><end>' timeSpanStop '</end></TimeSpan>',10 ];
    end

end

altitude = height;
radius = convert2degree(radius);
divisions = 2 .^ divisions;
angle_division = 360.0 / divisions;

header=['<Placemark ',id_chars,'>',10,...
    name_chars,10,...
    timeStamp_chars,...
    timeSpan_chars,...
    visibility_chars,10,...
    snippet_chars, ...
    description_chars,10,...
    region_chars, ...
    '',10,...
  '<Polygon ',poly_id_chars,'>',10,...
  '<extrude>1</extrude>',10,...
  altitudeMode_chars,...
    '<outerBoundaryIs>',10,...
      '<LinearRing>',10,...
      '<extrude>1</extrude>',10,...
        '<coordinates>',10,];

		coordinates = '';
		for i = divisions:-1:0

			angle = angle_division * i;
			[xS, yS] = vectorsplit( angle, radius );

			coordinates = [coordinates, sprintf('%.6f,%.6f,%.6f ', X+xS, Y+yS, altitude)];

		end

footer=['</coordinates>',10,...
      '</LinearRing>',10,...
    '</outerBoundaryIs>',10,...
  '</Polygon>',10,...
'</Placemark>',10];

output = [ header, coordinates, footer ];

function [output] = convert2degree(in)
%% convert2degree
% helper function that converts to decimal degree coordinates
    output = 180 * in / (6378137.0  * pi);

function [x, y] = vectorsplit( angle, magnitude )
% Splits the vector at angle & magnitude

alpharad = deg2rad( angle ); %[rad]

x = sin( alpharad ) * magnitude;
y = cos( alpharad ) * magnitude;


text:
Coronavirus in Illinois updates: COVID-19 restrictions loosened in Will and Kankakee counties and downstate region that includes Champaign-Urbana and Decatur
Coal-fired power plant in southern Illinois a major obstacle to Biden's push for carbon-free electricity by 2035
Biden revokes Trump's 1776 report promoting 'patriotic education,' which was mocked by some as propaganda
Column: A week after the Chicago Bears' astonishing state-of-the-franchise address, the city's ire has amplified. Do Chairman George McCaskey and CEO Ted Phillips see something everyone else doesn't?
Nonalcoholic beer sales growing — and it's not just Dry January. Is it finally ready to take off?
Column: Biden calls for an end to 'uncivil war,' but will he defend free speech?
As CTU begins vote on refusing in-person teaching, CPS says union 'wants to close schools that are already safely open'
Romney endorses Kirk as 'essential' to keeping Senate in GOP hands
By Kim Geiger
Chicago Tribune |
Senator Mark Kirk, seated, and Governor Mitt Romney, left, toured MATTER Wednesday October 19, 2016, a Chicago healthcare startup incubator providing innovators and entrepreneurs the opportunities to go beyond the status quo in healthcare to improve patients' lives. (Phil Velasquez / Chicago Tribune)
Former Gov. Mitt Romney described Sen. Mark Kirk as "an independent voice" who will "not stand for the kind of partisanship that has gridlocked Washington."
Former Massachusetts Gov. Mitt Romney visited Chicago on Wednesday to campaign for Republican Sen. Mark Kirk, saying it's "essential" that the GOP maintain control of the U.S. Senate to "keep America from going off the rails."
The Republican, who largely has stayed off the political stage since his failed 2012 challenge to President Barack Obama, reiterated a position he staked out earlier this year, that he will not support GOP nominee Donald Trump or Democrat Hillary Clinton in the Nov. 8 election.
Kirk, too, is among a number of Republicans who have rejected Trump's candidacy. Romney joked that he had considered writing his wife's name on his ballot, but said he would be "looking at other people running more seriously in the coming days."
Mark Kirk wants Donald Trump off ballot, but there's no way to remove him
Donald Trump reeled Friday under a barrage of major campaign missteps followed by revelations about lewd comments he made about women several years ago.
By By Philip Bump
In delivering his endorsement, Romney described Kirk as "an independent voice, a strong voice who will stand up for the people of Illinois," and "not stand for the kind of partisanship that has gridlocked Washington."
Kirk, for his part, ran with the theme of being above partisan politics by repeatedly pointing out that he has received low marks from the National Rifle Association and has been pushing legislation to criminalize gun trafficking.
"We've got to make sure that Chicago's no longer the headquarters of Murder, Inc., and make sure we have a senator who can be effective in the Senate to shut down supply of those weapons," said Kirk, who is in his first Senate term after serving for 10 years in the House.
"If I was a standard Republican, I would toe the NRA line," Kirk said. "I got an F-minus from the NRA. And with so much violence in this state, we've got to have somebody who can break loose from party ideology and advocate enough for this state."
Both Kirk and Democratic challenger U.S. Rep. Tammy Duckworth have received grades of F on the NRA score card, according to the organization's website.
Romney gave only brief remarks before touring a health-care startup incubator alongside Kirk and then quickly ducking out. With the Republican Party in the midst of an identity crisis fueled by Trump's controversial candidacy, the one-time Republican standard-bearer said his party has work to do to restore its image with voters.
"Depending on circumstances, we'll have to chart a course which will allow us to connect with more voters in the country," Romney said. "Look, the only way you win is by having minorities and women and young people, millennials, seniors feel that your party is the party that cares for them. And we do. And I do. The senator does."
kgeiger@chicagotribune.com
Twitter @kimgeiger
City watchdog says Animal Care and Control employee sexually assaulted 2 co-workers while off duty, supervisor did not report to higher-ups
The Spin: Biden calls for unity, end to 'uncivil war' | Twitter captivated by Obama-Harris picture on historic day | Trump bows out, vows 'we'll be back'

redpajama_set_name: RedPajamaCommonCrawl


text:
\section{Introduction}
\label{sec:introduction}

An important category of network indices
is based on the {\em distance} (the length of the shortest paths)
between every two vertices in the network.
It includes {\em closeness centrality},
{\em average path length},
{\em vertex eccentricity},
{\em average graph eccentricity}, etc.
Indices in this category have many important applications in different areas.
For example, in disease transmission networks,
closeness centrality is used to measure vulnerability to disease and infectivity \cite{Bell19991}.
In routing networks, vertex eccentricity is used to
determine vertices that form the periphery
of the network and have the largest worst-case response time
to any other device \cite{Magoni:2001:AAS:505659.505663,a6010100}.
In biological networks, vertices with high eccentricity
perceive changes in concentration of their neighbor enzymes or molecules \cite{Pavlopoulos2011}.

Using the length of shortest paths as the distance measure
has shortcomings.
A well-studied shortcoming is that
extending it to disconnected graphs (and also directed graphs)
is controversial \cite{Wasserman1994,Cornwell_complement_centrality,Rochat2009,Opsahl2010245}.
The other --less studied-- shortcoming is
that by using this measure,
a huge number of vertices may find exactly the same closeness/eccentricity score.
For instance, Shun \cite{Shun:2015:EPE:2783258.2783333} recently reported that around $30\%$
of the (connected) vertices of the Yahoo graph have the same non-zero eccentricity score.
Our experiments, reported in Section~\ref{sec:empiricaldiscriminability},
reveal that this happens in many real-world graphs.
This restricts the applicability of distance-based indices such as closeness and eccentricity,
as they cannot distinguish vertices.
For example, when closeness or eccentricity
are used for the facility location problem \cite{DBLP:conf/dagstuhl/KoschutzkiLPRTZ04},
they may not be able to distinguish one location among a set of candidate locations.
Finally, in many cases, the distance between two vertices not only
depends on the length of shortest paths,
but also on the number of shortest paths between them.
As a simple example, consider a network of locations
where edges are roads connecting the locations.
In a facility location problem, given two (or more) candidate locations,
we want to choose the one
which is more accessible from the rest of the network.
Then, we may prefer the location
which is slightly farther from the rest of the network but has more connections
to the location which is closest to the rest of the network.
In particular,
if two locations have exactly the same distance from the other locations,
the one connected to the rest of the network by more roads is preferred.

These observations motivate us to develop a new distance measure between vertices of a graph that yields
{\em more discriminative} centrality notions.
Furthermore, it considers both shortest path length and the number of shortest paths.
In this paper, our key contributions are as follows.
\begin{itemize}
\item
We propose new distance-based network indices,
including {\em discriminative closeness},
{\em discriminative path length},
{\em discriminative vertex eccentricity} and
{\em average discriminative graph eccentricity}.
These indices are proportional to the length of shortest paths and
inversely proportional to the number of shortest paths.
Our empirical evaluation of these notions reveals an interesting property of real-world networks.
While real-world graphs
have the \textbf{{small-world}} property
which means they have a small average path length bounded by the logarithm of the number of their vertices,
they usually have a considerably smaller average discriminative path length,
bounded by a constant (e.g., $2$).
We refer to this property as the \textbf{{tiny-world}} phenomena.
\item
We present algorithms for exact computation of the proposed discriminative indices.
We then develop a randomized algorithm that precisely estimate average discriminative path length
(and average discriminative eccentricity)
and show that it can give an $(\epsilon,\delta)$-approximation,
where $\epsilon \in \mathbb R^+$ and $\delta \in (0,1)$.

\item
We perform extensive experiments over several real-world networks from different domains.
First, we examine {\em discriminability} of our proposed indices and show that compared to the traditional indices,
they are usually much more discriminative\footnote{Note that
having a {\em total ordering} of the vertices is not always desirable and by
{\em discriminative indices}, we do not aim to do so.
Instead, we want to have a {\em partial ordering} over a {\em huge} number of vertices that
using traditional distance-based measures,
find exactly the same value.
}.
Second, we evaluate the empirical efficiency of our simple randomized algorithm for
estimating average discriminative path length
and show that it can very precisely estimate average discriminative path length,
using only few samples.
Third, we show that our simple randomized algorithm for
estimating average discriminative eccentricity
can generate high quality results, using only few samples.
This has analogy to the case of average eccentricity
where a simple randomized algorithm significantly
outperforms more advanced techniques \cite{Shun:2015:EPE:2783258.2783333}.

\item
In order to better motivate the usefulness of our proposed distance measure in real-world applications,
we present a novel {\em link prediction} method,
that uses discriminative distance to indicate which vertices are more likely to
form a link in future.
By running extensive experiments over several real-world datasets,
we show the superior performance of our method,
compared to the well-known existing methods.
\end{itemize}

The rest of this paper is organized as follows.
In Section~\ref{sec:preliminaries},
preliminaries and necessary definitions related to
distance-based indices are introduced.
A brief overview on related work is given in Section~\ref{sec:relatedwork}.
In Section~\ref{sec:discriminativecloseness},
we introduce our discriminative distance-based indices and discuss their extensions and properties.
We present exact and approximate algorithms for computing discriminative indices in Section~\ref{sec:algorithms}.
In Section~\ref{sec:experimentalresults}, we empirically evaluate
discriminability of our indices and the efficiency and accuracy of
our randomized algorithms.
In Section~\ref{sec:linkprediction},
we present our link prediction method
and show its superior performance.
Finally, the paper is concluded in Section~\ref{sec:conclusion}.

\section{Preliminaries}
\label{sec:preliminaries}

In this section, we present definitions and notations widely used in the paper.
We assume that the reader is familiar with basic concepts in graph theory.
Throughout the paper, $G$ refers to a graph (network).
For simplicity, we assume that $G$ is a connected, undirected and loop-free graph without multi-edges.
Throughout the paper, we assume that $G$ is an unweighted graph,
unless it is explicitly mentioned that $G$ is weighted.
$V(G)$ and $E(G)$ refer to the set of vertices and the set of edges of $G$, respectively.
We use $n$ and $m$ to refer to $|V(G)|$ and $|E(G)|$, respectively.
We denote the set of neighbors of a vertex $v$ by $\mathcal N(v)$.

A \textit{shortest path} (also called a \textit{geodesic path})
between two vertices $v,u \in V(G)$ is a path
whose length is minimum, among all paths between $v$ and $u$.
For two vertices $v,u \in V(G)$,
we use $d(v,u)$, to denote the {\em length} (the number of edges) of a shortest path connecting $v$ and $u$.
We denote by $\sigma(v,u)$ the number of shortest paths between $v$ and $u$.
By definition, $d(v,v)=0$ and $\sigma(v,v)=0$.
We use $deg(v)$ to denote the degree of vertex $v$.
The {\em diameter} of $G$, denoted by $\Delta(G)$, is defined as
$\max_{v,u \in V(G)} d(v,u)$.
The {\em radius} of $G$ is defined as
$\min_{v \in V(G)} \max_{ u \in V(G)\setminus\{v\}} d(v,u)$.

{\em Closeness} centrality of a vertex $v \in V(G)$ is defined as \cite{DBLP:conf/sdm/KangPST11}:\footnote{
The more common definition of {\em closeness centrality} is as follows \cite{DBLP:conf/alenex/BergaminiBCMM16}:
$C(v) = \frac{n-1}{\sum_{u\in V(G)\setminus\{v\}} d(v,u)}$.
In this paper, due to consistency with the definitions of
the other distance-based indices,
we use the definition
presented in Equation~\ref{eq:closeness}.
Note that this change has no effect on the results presented in the paper and they are
still valid for the more common definition of closeness.
}
\begin{equation}
\label{eq:closeness}
C(v) = \frac{1}{n-1} \sum_{u\in V(G)\setminus\{v\}} d(v,u).
\end{equation}
{\em Average path length} of graph $G$ is defined as \cite{doi:10.1137/S003614450342480}:
\begin{equation}
\label{eq:averagepathlength}
APL(G) = \frac{1}{n \times (n-1) }
\sum_{v \in V(G)} \sum_{u\in V(G)\setminus\{v\}} d(v,u).
\end{equation}
{\em Eccentricity} of a vertex $v \in V(G)$ is defined as \cite{NET:NET2,husfeldt:LIPIcs:2017:6947}:\footnote{Again,
while the common definition of {\em eccentricity} does not have the normalization factor
$\frac{1}{n-1}$, here in order to have consistent definitions for all the distance-based indices,
we add it to Equation~\ref{eq:eccentricity}.
}
\begin{equation}
\label{eq:eccentricity}
E(v) = \frac{1}{n-1} \max_{ u\in V(G)\setminus\{v\}}  d(v,u).
\end{equation}
{\em Average eccentricity} of graph $G$ is defined as \cite{NET:NET2,husfeldt:LIPIcs:2017:6947}:
\begin{equation}
\label{eq:eccentricitygraph}
AE(G) = \frac{1}{n \times (n-1)}\sum_{v\in V(G)} \max_{u\in V(G)\setminus\{v\}} d(v,u).
\end{equation}
{\em Center} of a graph is defined as the set of vertices that have the minimum
eccentricity.
{\em Periphery} of a graph is defined as the set of vertices that have the maximum
eccentricity.

\section{Related work}
\label{sec:relatedwork}

The widely used distance-based indices are
{\em closeness} centrality, {\em average path length}, {\em eccentricity} and
{\em average eccentricity} defined in Section~\ref{sec:preliminaries}.
In all these indices, it is required to compute the distance between every pair of vertices.
The best algorithm in theory for solving all-pairs shortest paths
is based on matrix multiplication \cite{DBLP:conf/stoc/Williams12}
and its time complexity is $O(n^{2.3727})$.
However, in practice breadth first search (for unweighted graphs)
and Dijkstra's algorithm (for weighted graphs with positive weights)
are more efficient.
Their time complexities for all vertices are $O(nm)$ and $O(nm+n^2 \log n)$, respectively.
In the following, we briefly review exact and inexact algorithms proposed
for computing closeness and eccentricity.

\subsection{Closeness centrality and average path length}
Eppstein and Wang \cite{DBLP:journals/jgaa/EppsteinW04} presented a uniform sampling algorithm
that with high probability
approximates the inverse closeness centrality
of all vertices in a weighted graph $G$ within an additive error
$\epsilon \Delta(G)$.
Their algorithm requires $O(\frac{\log n}{\epsilon^2})$ samples and
spends $O(n\log n+m)$ time to process each one.
Brandes and Pich \cite{jrnl:Brandes3}
extended this sampler by considering different
non-uniform ways of sampling.
Cohen et.al. \cite{Cohen:2014:CCC:2660460.2660465} combined the sampling method with the
{\em pivoting} approach \cite{Cohen:2000:PNW:331605.331610} and \cite{Ullman:1991:HPP:103123.103129},
where pivoting is used for the vertices
that are far from the given vertex.
Olsen et.al. \cite{DBLP:conf/icde/OlsenLH14} suggested
storing and re-using the intermediate results
that are common among different vertices.
Okamoto et.al. \cite{DBLP:conf/faw/OkamotoCL08}
presented an algorithm for
ranking top $k$ highest closeness centrality vertices
that runs in $O((k + n^{\frac{2}{3}} \log^{\frac{1}{3}} n)(n\log n + m) )$ time.
There are several extensions of closeness centrality for specific networks.
Kang et.al. \cite{DBLP:conf/sdm/KangPST11}
defined closeness centrality of a vertex $v$ as the
(approximate) average distance from $v$ to all other vertices in the graph
and proposed algorithms to compute it in \textsc{MapReduce}.
Tarkowski et.al. \cite{DBLP:conf/aaai/TarkowskiSRMW16} developed a game-theoretic
extension of closeness centrality
to networks with community structure.

\subsection{Eccentricity and average eccentricity}

Dankelmann et.al. \cite{Dankelmann:2004} showed that the average eccentricity of a graph is at least
$\frac{9n}{4(deg_{m}+1)}+O(1)$,
where $deg_{m}$ is the minimum degree of the graph.
Roditty and Williams \cite{Roditty:2013:FAA:2488608.2488673} developed an algorithm that gives an estimation
$\hat{E}(v)$ of the eccentricity of vertex $v$ in an undirected and unweighted graph,
such that $\hat{E}(v)$ is bounded as follows: $\frac{2}{3}E(v) \leq \hat{E}(v) \leq \frac{3}{2}E(v)$.
Time complexity of this algorithm is
$O(m \sqrt{n \log n})$.
Takes and Kosters \cite{a6010100} presented
an exact eccentricity computation algorithm,
based on lower and upper bounds on the eccentricity of each vertex of the graph.
They also presented a pruning technique
and showed that it can significantly improve upon the standard algorithms.
Chechik et.al. \cite{Chechik:2014:BAA:2634074.2634152} introduced an
$O(\left(m \log m \right)^{3/2} )$ time
algorithm that gives an estimate $\hat{E}(v)$ of
the eccentricity of vertex $v$ in an undirected and weighted graph,
such that $\frac{3}{5}E(v) \leq \hat{E}(v) \leq E(v)$.
Shun \cite{Shun:2015:EPE:2783258.2783333} compared shared-memory parallel implementations
of several average eccentricity approximation algorithms.
He showed that in practice a two-pass simple algorithm
significantly outperforms more advanced algorithms
such as \cite{Roditty:2013:FAA:2488608.2488673} and \cite{Chechik:2014:BAA:2634074.2634152}.

\section{Discriminative distance-based indices}
\label{sec:discriminativecloseness}

In this section, we present the family of discriminative distance-based indices.
\subsection{Indices}
\label{sec:indices}
The first index is {\em discriminative closeness} centrality.
Similar to closeness centrality,
discriminative closeness is based on the length of shortest paths between different
vertices in the graph.
However, unlike closeness centrality,
discriminative closeness centrality considers the number of shortest paths, too.
For a vertex $v \in V(G)$,
{\em discriminative closeness} of $v$, denoted with $DC(v)$, is formally defined as follows:

\begin{equation}
\label{eq:discriminativecloseness}
DC(v) = \frac{1}{n-1} \sum_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)}.
\end{equation}

If in the definition of average path length,
closeness centrality is replaced by
discriminative closeness centrality defined in Equation~\ref{eq:discriminativecloseness},
we get {\em average discriminative path length} of $G$,
defined as follows:

\begin{equation}
\label{eq:averagediscriminativepathlength}
ADPL(G) = \frac{1}{n \times (n-1) }
\sum_{v \in V(G)} \sum_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)}.
\end{equation}

In a similar way, {\em discriminative eccentricity} of a vertex $v \in V(G)$,
denoted by $DE(v)$,
is defined as follows:

\begin{equation}
\label{eq:discriminativeeccentricity}
DE(v) = \frac{1}{n-1} \max_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)}.
\end{equation}

Finally, {\em average discriminative eccentricity} of $G$
is defined as follows:

\begin{equation}
\label{eq:discriminativeeccentricitygraph}
ADE(G) = \frac{1}{n \times (n-1)}\sum_{v\in V(G)} \max_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)}.
\end{equation}

All these notions are based on replacing {\em distance} by
{\em discriminative distance},
defined as follows.
For $v,u\in V(G)$, {\em discriminative distance} between $v$ and $u$,
denoted with $dd(v,u)$,
is defined as $\frac{d(v,u)}{\sigma(v,u)}$.
We define {\em discriminative diameter} and {\em discriminative radius} of $G$
respectively as follows:

\begin{equation}
\label{eq:discriminativediaeter}
DD(G) = \max_{v\in V(G)} \max_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)},
\end{equation}

\begin{equation}
\label{eq:discriminativeradius}
DR(G) = \min_{v\in V(G)} \max_{u\in V(G)\setminus\{v\}} \frac{d(v,u)}{\sigma(v,u)}.
\end{equation}

Finally,
we define {\em discriminative center} of a graph as the set of vertices that have the minimum
discriminative eccentricity; and
{\em discriminative periphery} of a graph as the set of vertices that have the maximum
discriminative eccentricity.

\paragraph{\textbf{Generalizations}}
We can consider two types of generalizations of
Equations~\ref{eq:discriminativecloseness}-\ref{eq:discriminativeradius}.
In the first generalization, in the denominator of the equations,
instead of using the number of shortest paths, we may use
the number of a restricted class of shortest paths, e.g., vertex disjoint shortest paths,
edge disjoint shortest paths etc.
In the second generalization, instead of directly using distances and the number of shortest paths,
we may introduce and use functions $f$ and $g$,
defined respectively on the length and the number of shortest paths.
Then, by changing the definitions of $f$ and $g$,
we can switch among different distance-based notions.
For example, for any two vertices $v,u \in V(G)$,
if $f(d(v,u))$ and $g(\sigma(v,u))$
are respectively defined as $d(v,u)$ and $1$,
we will have the traditional distance-based indices introduced in Section~\ref{sec:preliminaries}.
If $f(d(v,u))$ and $g(\sigma(v,u))$
are respectively defined as $\frac{1}{d(v,u)}$ and $1$,
we will have {\em harmonic closeness} centrality \cite{Rochat2009}
defined as follows:
\[HC(v)=\frac{1}{n-1} \sum_{u\in V(G) \setminus \{v\}} \frac{1}{d(v,u)}.\]
Then, someone may define {\em discriminative harmonic closeness} centrality of vertex $v$ as:

\begin{equation}
\label{eq:discriminativeharmoniccloseness}
DHC(v) = \frac{1}{n-1} \sum_{u \in V(G) \setminus \{v\}} \frac{\sigma(v,u)}{d(v,u)},
\end{equation}
where $f(d(v,u))$ and $g(\sigma(v,u))$
are respectively defined as $\frac{1}{d(v,u)}$ and $\frac{1}{\sigma(v,u)}$.

\paragraph{\textbf{Connection to the other indices}}
Path-based indices such as {\em betweenness centrality} \cite{DBLP:journals/cj/Chehreghani14,bcd}
(and its generalizations such as {\em group betweenness} centrality \cite{doi:10.1080/10556788.2016.1167892}
and {\em co-betweenness} centrality \cite{conf:cbcwsdm})
consider the number of shortest paths that pass over a vertex.
However, betweenness centrality does not consider the shortest path length and it is used as an indicator of
the amount of control that a vertex has over shortest paths in the network.
Some variations of betweenness centrality, such as {\em length-scaled betweenness centrality}
and {\em linearly scaled betweenness centrality} \cite{Brandes08onvariants},
are more similar to our proposed notions.
However, they still measure the amount of control that a vertex has over shortest paths,
but give a weight (which is a function of distance)
to the contribution of each shortest path.
In our proposed notions, the number of shortest paths passing over a vertex
does not always contribute to the centrality of the vertex.
Indices such as {\em Katz centrality} \cite{Katz1953} and
{\em personalized PageRank} \cite{Haveliwala:2002:TP:511446.511513}
consider both the length and the number of paths between two vertices.
However, there are important differences, too.
For example, Katz centrality is proportional to both the length and the number of paths.
Furthermore, it considers all paths. This makes it inappropriate for the
applications where the concept of shortest paths is essential.
This index is mainly used in the analysis of directed acyclic graphs.
If in the Katz index of two vertices $v$ and $u$, denoted by $K(v,u)$,
the paths are limited to shortest paths (and the bias constant $\beta$ is set to $0$),
we can express it using our generalization of discriminative indices.
If this limitation is applied, $K(v,u)$ will be defined as $\alpha^{d(v,u)}\sigma(v,u)$, where
$\alpha$ is the {\em attenuation factor} \cite{Katz1953}.
Then, this index can be seen as a special case of our generalized discriminative index,
where $f(d(v,u))$ is defined as $\alpha^{d(v,u)}$ and
$g(\sigma(v,u))$ is defined as $\frac{1}{\sigma(v,u)}$.

The other index that may have some connection to our discriminative indices is
{\em clustering coefficient} \cite{watts1998cds}.
Both clustering coefficient and discriminative indices are sensitive to the local density of the vertices, however,
they have different goals.
While clustering coefficient aims to directly reflect the local density,
discriminative indices aim to take into account the density of different regions of the graph,
when computing distances.

\paragraph{\textbf{Disconnected or directed graphs}}
When the graph is disconnected or directed,
it is possible that there is no (shortest) path between vertices $v$ and $u$.
In this case, $d(v,u)=\infty$ and $\sigma(v,u)=0$, hence, $\frac{d(v,u)}{\sigma(v,u)}$ is undefined.
For closeness centrality, when $d(v,u)=\infty$,
a first solution is to define $d(v,u)$ as $n$.
The rationale is that in this case $d(v,u)$ is a number
greater than any shortest path length.
We can use a similar technique for discriminative distance:
when there is no path from $v$ to $u$,
we define $d(v,u)$ as $n$
and $\sigma(v,u)$ as $1$.
This discriminative distance will be greater than the
discriminative distance between any two vertices $v'$ and $u'$
that are connected by a path from $v'$ to $u'$.
The second solution suggested for closeness centrality is to use harmonic centrality \cite{Rochat2009}.
As stated in Equation~\ref{eq:discriminativeharmoniccloseness},
this can be applied to discriminative closeness, too.
When $d(v,u)=\infty$, Equation~\ref{eq:discriminativeharmoniccloseness} yields $\frac{0}{\infty}$,
which is conventional to define as $0$.

\begin{figure}
\centering
\subfigure[]
{
\includegraphics[scale=0.5]{example1}
\label{fig:example1}
}\qquad\qquad
\subfigure[]
{
\includegraphics[scale=0.5]{example2}
\label{fig:example2}
}
\caption
{
\label{figure:example}
In \ref{fig:example1}, we have: $dd(v,u)<dd(v,w)+dd(w,u)$ and in \ref{fig:example2},
we have: $dd(v,u)=dd(v,w)+dd(w,u)$.}
\end{figure}

\paragraph{\textbf{A property}}
A nice property of shortest path length is that
for vertices $v,u,w \in V(G)$
such that $w$ is on a shortest path between $v$ and $u$,
the following holds: $d(v,u) = d(v,w)+d(w,u)$.
This property is useful in e.g., designing efficient distance computation algorithms.
This property does not hold for discriminative distance as
$dd(v,u)$ can be less than or equal to $dd(v,w)+dd(w,u)$.
An example is presented in Figure~\ref{figure:example}.
However, we believe this is not a serious problem.
The reason is that more than shortest path length that satisfies the above mentioned property,
discriminative distance is based on the number of shortest paths,
which satisfies the following property: $\sigma_w(v,u)=\sigma(v,w) \times \sigma(w,u)$,
where $\sigma_w(v,u)$ is the number of shortest paths between $v$ and $u$ that pass over $w$.
As we will discuss in Section~\ref{sec:algorithms}, these two properties can help us
to design efficient algorithms for computing discriminative distance-based indices.

\begin{figure}
\centering
\includegraphics[scale=0.5]{exponential}
\caption{\label{figure:exponential}
There are $2^{(n/2)-1}$ shortest paths between $s$ and $t$.}
\end{figure}

\paragraph{\textbf{Why our proposed indices are more discriminative}}
It is very difficult to theoretically prove that for general graphs,
our proposed indices are always more discriminative
than the existing distance-based indices.
However, we can still provide arguments explaining why in practice
our proposed indices are more discriminative.
We here focus on unweighted graphs.
Let $n$ be the number of vertices.
While the maximum possible shortest path length in a graph is $n-1$,
for real-world networks it is much smaller and it is $\log n$.
This means the range of all possible values of distance is narrow and as a result,
a vertex may have the same distance from many other vertices.
This yields that many vertices may have the same closeness/eccentricity scores.
However, the range of all possible values of the number of shortest paths between two vertices is much wider
and it varies between $1$ and an exponential function of $n$.
For example, on the one hand, in the graph of Figure~\ref{figure:exponential},
there are $2^{(n/2)-1}$ shortest paths between $s$ and $t$ and
on the other hand, in a tree there is only one shortest path between any two vertices.
This wider range yields that when the number of shortest paths is involved, the probability
that two vertices have exactly the same score drastically decreases.

\subsection{\textbf{Intuitions}}
\label{sec:intuitions}

In several cases, the distance between two vertices in the graph not only depends on
their shortest path length, but also (inversely) on the number of shortest paths they have.
In the following, we discuss some of them.

\paragraph{Time and reliability of traveling}
A key issue in transportation and logistics \cite{Polus1979,Bonsall1997371}
and in vehicular social networks (VSNs) \cite{DBLP:journals/cm/NingXUKH17} is
to estimate the {\em traveling time} and {\em route reliability}
between two points $A$ and $B$.
The time and reliability of traveling from $A$ to $B$
depend on the structure of the road network and also on the stochastic factors such as
weather, traffic incidents.
One of the factors that depends on the network structure is the
number of ways that someone can travel from $A$ to $B$.
Having several ways to travel from $A$ to $B$, on the one hand, increases the reliability of traveling.
On the other hand, it deceases traffic between $A$ and $B$ and as a result, the traveling time.
Therefore, taking into account both the length and the number of shortest paths between $A$ and $B$
(in other words, defining the distance between $A$ and $B$
in terms of both the length and the number of shortest paths)
can help to better estimate the time and reliability of traveling between $A$ and $B$.

\paragraph{Spread of infections}
It it known that
infection and contact rates in a network depend on the community structure of the network and
the spread of infections
inside a community is faster \cite{CIS-138118,Pellis2011,0295-5075-72-2-315}.
Consider vertices $v_1$, $v_2$ and $v_3$ such that $d(v_1,v_2)=d(v_1,v_3)$,
$v_1$ and $v_2$ are in the same community but $v_1$ and $v_3$ are not.
An infection from $v_1$ usually spreads to $v_2$ faster than $v_3$,
or the probability that (after some time steps) $v_2$ becomes infected by $v_1$ is higher than
the probability that $v_3$ becomes infected.
Here, to describe the distances between the vertices,
our discriminative distance measure is a better notion than the shortest path length.
Vertices $v_1$ and $v_2$ that are inside a community are heavily connected and as a result,
they usually have many shortest paths between themselves.
In contrast, $v_1$ and $v_3$ do not belong to the same community and are not heavily connected,
hence, they usually have less shortest paths between themselves.
This means $dd(v_1,v_2)$ is smaller than $dd(v_1,v_3)$, which is consistent with
the infection rate.

\section{Algorithms}
\label{sec:algorithms}

In this section, we discuss how discriminative indices can be computed.
First in Section~\ref{sec:exactalgorithm}, we present the exact algorithms
and then in Section~\ref{sec:randomized}, we present the approximate algorithms.

\subsection{Exact Algorithms}
\label{sec:exactalgorithm}

In this section, we present the \textsf{DCC}\footnote{\textsf{DCC} is an abbreviation
for \textbf{D}iscriminative \textbf Closeness \textbf Calculator.}
algorithm for computing
{\em discriminative closeness} centrality of all vertices of the network
and show how it can be revised to compute the other discriminative indices.

\begin{algorithm}
\caption{High level pseudo code of the algorithm of computing
{\em discriminative closeness} scores.}
\label{algorithm:dc3}
\begin{algorithmic} [1]
\STATE \textsf{DCC}
\STATE \textbf{Input.} A network $G$.
\STATE \textbf{Output.} {\em Discriminative closeness} centrality of vertices of $G$.
\FORALL {vertex $v \in V(G)$}
\STATE $I[v] \leftarrow 0$.
\ENDFOR
\FORALL {vertex $v \in V(G)$} \label{line:dcc:loop1}
\STATE $D,N \leftarrow \text{\textsc{ShortestPathDAG}}(G,v).$
\FORALL {vertex $u \in V(G)\setminus \{v\}$}
\STATE $I[v] \leftarrow I[v] + \frac{1}{n-1} \times \frac{ D[u] }{N[u]}$. \label{line:dcc:mainoperation}
\ENDFOR
\ENDFOR \label{line:dcc:loop2}
\RETURN $I$.
\item[]
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{algorithm:dc3} shows the high level pseudo code of
the algorithm.
\textsf{DCC} is an iterative algorithm
where at each iteration,
discriminative closeness of a vertex $v$ is computed.
This is done by calling the \textsf{ShortestPathDAG} method for $v$.
Inside \textsf{ShortestPathDAG}, the distances and the number of shortest paths
between $v$ and all other vertices in the graph are computed.
If $G$ is unweighted, this is done by a breadth-first search starting from $v$.
Otherwise, if $G$ is weighted with positive weights,
this is done using Dijkstra's algorithm \cite{Dijkstra1959}.
A detailed description of
\textsf{ShortestPathDAG} can be found in several graph theory books, including \cite{Diestel},
hence, we here ignore it.

\paragraph{Computing the other indices}
Algorithm~\ref{algorithm:dc3} can be revised to compute
{\em average discriminative path length} of $G$,
{\em discriminative eccentricity} of vertices of $G$
and {\em average discriminative eccentricity} of $G$.
\begin{itemize}
\item
$ADPL(G)$.
After Line~\ref{line:dcc:loop2} of Algorithm~\ref{algorithm:dc3}
(where the $I[v]$ values are already computed),
$ADPL(G)$
can be computed as $\frac{\sum_{v \in V(G)} I[v]}{n}$.

\item
$DE(v)$.
If Line~\ref{line:dcc:mainoperation} of Algorithm~\ref{algorithm:dc3}
is replaced by the following lines:
\begin{center}
\begin{algorithmic}
\IF{$\frac{1}{n-1} \times \frac{D[u]}{N[u]} > I[v]$}
\STATE $I[v] \leftarrow \frac{1}{n-1} \times \frac{D[u]}{N[u]}$.
\ENDIF
\end{algorithmic}
\end{center}

then, the algorithm will compute discriminative eccentricity of the vertices of $G$
and will store them in $I$.

\item
$ADE(G)$.
After computing {\em discriminative eccentricity} of all vertices of $G$ and
storing them in $I$,
$ADE(G)$ can be computed as
$\frac{\sum_{v \in V(G)} I[v]}{n}$.
\end{itemize}

In a similar way, Algorithm~\ref{algorithm:dc3} can be revised
to compute discriminative diameter and discriminative radius of $G$.

\paragraph{Complexity analysis}
For unweighted graphs, each iteration of the loop in Lines~\ref{line:dcc:loop1}-\ref{line:dcc:loop2}
of method \textsc{DCC}
takes $O(m)$ time.
For weighted graphs with positive weights, using a Fibonnaci heap,
it takes $O(m+n \log n)$ time \cite{Diestel}.
This means discriminative closeness centrality and discriminative eccentricity of a given vertex
can be computed respectively in $O(m)$ time and $O(m+n \log n)$ time
for unweighted and weighted graphs with positive weights.
However, computing average discriminative path length and/or average eccentricity of the graph
requires respectively $O(nm)$ time and $O(nm+n^2 \log n)$ time
for unweighted graphs and weighted graphs with positive weights.
Space complexity of each iteration (and the whole algorithm), for both unweighted graphs
and weighted graphs with positive weights, is $O(n+m)$ \cite{Diestel}.
Note that these complexities are the same as complexities
of computing traditional distance-based indices.
The reason is that
in addition to computing the distances between $v$ and all other vertices of the graph,
\textsf{ShortestPathDAG} can also compute the number of shortest paths,
without having any increase in the complexity \cite{Diestel}.

\subsection{Randomized Algorithms}
\label{sec:randomized}

While discriminative closeness and discriminative eccentricity of a given vertex can be computed
efficiently,
the algorithms of computing average discriminative path length and
average discriminative eccentricity of the graph are
expensive in practice, even for mid-size networks.
This motivates us to present randomized algorithms
for ADPL and ADE that can be performed much faster,
at the expense of having approximate results.

\begin{algorithm}
\caption{High level pseudo code of the algorithm of
estimating {\em average discriminative path length}.}
\label{algorithm:apl}
\begin{algorithmic} [1]
\STATE \textsf{RandomADPL}
\STATE \textbf{Input.} A network $G$ and the number of samples $T$.
\STATE \textbf{Output.} Estimated {\em average discriminative path length} of $G$.
\STATE $\beta \leftarrow 0$.
\FORALL{$t=1$ \textbf{to} $T$ } \label{line:loop1}
\STATE Select a vertex $v \in V(G)$ uniformly at random.
\STATE $D,N \leftarrow \text{\textsf{ShortestPathDAG}}(G,v)$.
\STATE $\beta_t \leftarrow \frac{1}{n-1} \times \sum_{u\in V(G)\setminus \{v\}} \frac{D[u]}{N[u]}$. \label{line:apl:main}
\STATE $\beta \leftarrow \beta + \beta_t $.
\ENDFOR \label{line:loop2}
\STATE $\beta \leftarrow \frac{\beta}{T}$.
\RETURN $\beta$.
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{algorithm:apl} shows the high level pseudo code of
the \textsf{RandomADPL} algorithm, proposed to estimate average discriminative path length.
The inputs of the algorithm are the graph $G$ and the number of samples (iterations) $T$.
In each iteration $t$, the algorithm first chooses a vertex $v$ uniformly at random and
calls the \textsf{ShortestPathDAG} method for $v$ and $G$,
to compute distances and the number of shortest paths
between $v$ and any other vertex in $G$.
Then, it estimates average discriminative path length of $G$ at iteration $t$ as
$\frac{1}{n-1}\times \sum_{u\in V(G)\setminus \{v\}} \frac{d(v,u)}{\sigma(v,u)}$
and stores it in $\beta_t$.
The average of all $\beta_t$ values computed during
different iterations gives the final estimation $\beta$ of
average discriminative path length.
Clearly, for unweighted graphs,
time complexity of Algorithm \ref{algorithm:apl} is $O(T \times m)$ and
for weighted graphs with positive weights,
it is $O(T \times m + T \times n \log n)$.
In a way similar to Algorithm~\ref{algorithm:dc3}, Algorithm~\ref{algorithm:apl} can be modified to estimate
{\em discriminative eccentricity} of graph $G$,
where the details are omitted.

In the rest of this section, we provide an error bound for our estimation of
{\em average discriminative path length}.
First in Proposition~\ref{proposition:expectedvalue},
we prove that in Algorithm~\ref{algorithm:apl} the expected value of $\beta$ is $ADPL(G)$.
Then in Proposition~\ref{proposition:errorbound},
we provide an error bound for $\beta$.

\begin{proposition}
\label{proposition:expectedvalue}
In Algorithm~\ref{algorithm:apl}, expected value of $\beta_t$'s ($1\leq t \leq T$)
and $\beta$ is $ADPL(G)$.
\end{proposition}

\begin{proof}
We have:
\begin{align*}
\mathbf E\left[\beta_t\right] &= \sum_{v \in V(G)}
\left( \frac{1}{n} \times \frac{\sum_{u\in V(G)\setminus \{v\}} \frac{d(v,u)}{\sigma(v,u)} }  {n-1} \right)
                 = ADPL(G),
\end{align*}
where $\frac{1}{n}$ comes from the uniform distribution used to choose vertices of $G$.
Then, we have:
$\mathbf E\left[\beta\right] = \frac{\sum_{t=1}^T \mathbf E\left[\beta_t\right]}{T}
                 = \frac{T \times \mathbf E\left[\beta_t\right]}{T} = ADPL(G). $
\end{proof}

\begin{proposition}
\label{proposition:errorbound}
In Algorithm~\ref{algorithm:apl}, let $G$ be a connected and undirected graph.
For a given $\epsilon \in \mathbb R^+$, we have:
\begin{equation}
\label{eq:errorbound}
\mathbf P\left[\left| ADPL(G) - \beta \right| > \epsilon \right] \leq
2\exp \left( -2 \times T \times  \left( \frac{\epsilon}{\Delta(G)} \right)^2  \right).
\end{equation}
\end{proposition}

\begin{proof}
The proof is done using Hoeffding's inequality \cite{Hoeffding:1963}.
Let $X_1, \ldots, X_n$ be independent random variables bounded by the interval
$[a, b]$, i.e., $a \leq X_i \leq b$ ($1 \leq i \leq n$).
Let also $\bar{X}=\frac{1}{n}\left( X_1 + \ldots + X_n \right)$.
Hoeffding \cite{Hoeffding:1963} showed that:
\begin{equation}
\label{eq:hoeffding}
\mathbf P\left[ \left| \mathbf E\left[ \bar{X} \right] - \bar{X} \right| > \epsilon \right] \leq
2 \exp \left( -2 n \left( \frac{\epsilon}{b-a} \right)^2 \right).
\end{equation}

On the one hand,
for any two distinct vertices $v,u \in V(G)$, we have: $d(v,u) \leq \Delta(G)$
and $\sigma(v,u) \geq 1$.
Therefore, $\frac{d(v,u)}{\sigma(v,u)} \leq \Delta(G)$ and as a result,
$\beta_t \leq \Delta(G)$ ($1 \leq t \leq T$).
On the other hand,
for any two distinct vertices $v,u \in V(G)$, we have:
$\frac{d(v,u)}{\sigma(v,u)}>0 $. Therefore, $\beta_t>0$, for $1 \leq t \leq T$.
Note that in Algorithm~\ref{algorithm:apl} vertices $u$
are chosen independently and therefore,
variables $\beta_t$ are independent.
Hence, we can use Hoeffding's inequality,
where
$X_i$'s are $\beta_t$'s,
$\bar{X}$ is $\beta$,
$n$ is $T$,
$a$ is $0$ and
$b$ is $\Delta(G)$.
Putting these values into Inequality~\ref{eq:hoeffding}
yields Inequality~\ref{eq:errorbound}.
\end{proof}

Real-world networks have a small diameter,
bounded by the logarithm of the number of vertices in the network \cite{watts1998cds}.
This, along with Inequality~\ref{eq:errorbound}, yields\footnote{Note that
in Inequality~\ref{eq:errorbound2},
both $\beta$ and $\epsilon$ are in $\mathbb R^+$ and
since $\beta$ and its expected value are not bounded by $(0,1)$ and
they are considerably larger than 0 (and they can be larger than 1),
$\epsilon$ is usually set to a value much larger than 0 (and even larger than 1,
such as $\log n$).}:
\begin{equation}
\label{eq:errorbound2}
\mathbf P\left[\left| ADPL(G) - \beta \right| > \epsilon \right] \leq 2\exp
\left( -2 \times T \times  \left( \frac{\epsilon}{\log n} \right)^2  \right).
\end{equation}

Inequality~\ref{eq:errorbound2} says that for given
values $\epsilon \in \mathbb R^+$ and $\delta \in (0,1)$,
if $T$ is chosen such that
$T \geq
\frac{\ln\left(\frac{2}{\delta} \right) \left(\log n \right)^2}{2 {\epsilon}^2 },$
Algorithm~\ref{algorithm:apl} estimates
average discriminative path length of $G$
within an additive error $\epsilon$ with a probability at least $\delta$.
Our extensive experiments reported in Table~\ref{table:dataset} of
Section~\ref{sec:experimentalresults} (the rightmost column)
show that many real-world networks have a very small {\em discriminative diameter},
much smaller than the logarithm of the number of vertices they have.
So, we may assume that their discriminative diameter is bounded by a constant $c$.
For such networks,
using only $\frac{c^2 \times \ln\left(\frac{2}{\delta} \right) }{2 {\epsilon}^2 }$ samples,
Algorithm~\ref{algorithm:apl} can estimate
average discriminative path length
within an additive error $\epsilon$ with a probability at least $\delta$.

\makesavenoteenv{tabular}
\makesavenoteenv{table}

\begin{table*}
\caption{\label{table:dataset}Specifications of the largest component of the real-world datasets.}
\begin{center}
\begin{tabular}{ l | p{8.5cm} l l p{2cm}}
\hline
Dataset & Link & \# vertices & \# edges & Discriminative diameter  \\
\hline
dblp0305 & \url{http://www-kdd.isti.cnr.it/GERM/}  & 109,045 & 233,962 & 2 \\
dblp0507 &\url{http://www-kdd.isti.cnr.it/GERM/}  & 135,116 & 290,364  & 2 \\
dblp9202 & \url{http://www-kdd.isti.cnr.it/GERM/} & 129,074 & 277,082   & 2\\
facebook-uniform & \url{http://odysseas.calit2.uci.edu/doku.php/public:online_social_networks} & 134,304 & 135,532  & 2 \\

flickr & \url{http://konect.uni-koblenz.de/networks/flickrEdges} & 73,342 & 2,619,711  & 5 \\

gottron-reuters & \url{http://konect.uni-koblenz.de/networks/gottron-reuters} & 38,677 & 978,461  & 5 \\
petster-friendships & \url{http://konect.uni-koblenz.de/networks/petster-friendships-cat}  &  148,826 & 5,449,508  & 8 \\
pics\_ut & \url{http://konect.uni-koblenz.de/networks/pics_ut} & 82,035 & 2,300,296  &  5 \\
web-Stanford & \url{http://snap.stanford.edu/data/web-Stanford.html} & 255,265 & 2,234,572  & 16 \\
web-NotreDame & \url{http://snap.stanford.edu/data/web-NotreDame.html} & 325,729 & 1,524,589  & 28 \\
citeulike-ut & \url{http://konect.uni-koblenz.de/networks/citeulike-ut} & 153,277 & 2,411,940  & 7 \\
epinions & \url{http://konect.uni-koblenz.de/networks/epinions} & 119,130 & 834,000  &  15 \\
wordnet & \url{http://konect.uni-koblenz.de/networks/wordnet-words} & 145,145 & 656,230   & 15 \\
\hline
\end{tabular}
\end{center}
\end{table*}

\begin{table*}
\caption{\label{table:discriminability}
Comparison of {\em discriminability} of the centrality notions
over different real-world networks.
For each dataset, the most discriminative index is highlighted in bold.
}
\centering
\begin{tabular}{ l | p{2.1cm}  l l p{2.2cm} p{2.3cm} l }
\hline \hline
Database & Discriminative closeness &  Closeness & Betweenness & Length scaled betweenness & Linearly scaled betweenness & Katz \\
\hline
dblp0305  & $\bf{2.7805}$ & $0.0201$ & $0.0403$ & $0.0403$ & $0.0403$  & $0.4447$ \\
dblp0507   &  $\bf{2.7013}$ & $0.0155$ & $0.0325$ & $0.0325$ & $0.0325$   & $0.3804$ \\
dblp9202   &  $\bf{3.2973}$ & $0.0147$ & $0.0263$ & $0.0263$ & $0.0263$  & $0.3091$ \\
facebook-uniform   &  $\bf{5.6178}$ & $0.0446$ & $0.0528$ & $0.0528$  & $0.0528$  &  $0.9039$ \\
flickr  &  $\bf{92.7694}$ & $4.4435$ & $84.8381$ & $85.0835$  & $85.0835$  & $90.4365$ \\
gottron-reuters   &  $\bf{88.9934}$ & $25.8810$ & $74.3956$ & $74.3956$  & $74.3956$  & $88.9753$ \\
petster-friendships  &  $\bf{70.0764}$ & $39.2176$ & $65.7049$ & $65.7317$ & $65.7317$  & $70.0260$ \\
pics\_ut &  $\bf{50.5113}$ &  $36.3552$ & $33.4028$ & $33.5210$  & $33.5210$  & $42.6196$ \\
web-Stanford  &  $\bf{97.3376}$ & $18.9258$ & $26.6542$ & $27.2861$  & $27.2861$  &  $31.6122$ \\
web-NotreDame  &  $\bf{29.9819}$ & $18.5230$ & $18.1245$ & $19.2402$  & $19.2402$  & $19.0277$ \\
citeulike-ut  &  $\bf{45.2540}$ & $30.4546$ & $28.6135$ & $28.7185$  & $28.7185$  & $34.3032$ \\
epinions  &  $\bf{70.0218}$  & $57.0679$ & $42.1220$ & $45.5745$  & $45.5745$  & $60.1922$ \\
wordnet  &  $\bf{58.8907}$ & $51.8770$ & $38.8838$ & $40.5187$  &  $40.5187$  & $52.8340$ \\
\hline \hline
\end{tabular}
\end{table*}

\begin{figure*}
\centering
\includegraphics[scale=0.5]{time}
\caption
{\label{fig:time}
Running time of computing discriminative closeness centrality, closeness centrality and
betweenness centrality (and its variations).
The vertical axis is in logarithmic scale.}
\end{figure*}

\section{Experimental results}
\label{sec:experimentalresults}

We perform extensive experiments
on real-world networks to assess
the quantitative and qualitative behavior of our proposed algorithms.
The programs are compiled by the GNU C++ compiler 5.4.0 using optimization level 3.
We do our tests over (largest connected components of)
several real-world datasets from different domains, including
the {\em dblp0305}, {\em dblp0507} and {\em dblp9202}
co-authorship networks \cite{Berlingerio:conf},
the {\em facebook-uniform} social network \cite{Gjoka:conf},
the {\em flickr} network \cite{konect:McAuley2012},
the {\em gottron-reuters} network \cite{konect:reuters1},
the {\em petster-friendships} network \cite{konect},
the {\em pics\_ut} network \cite{konect},
the {\em web-Stanford} network \cite{jrnl:Leskovec3},
the {\em web-NotreDame} network \cite{albert1999dww},
the {\em citeulike-ut} network \cite{konect:emamy07},
the {\em epinions} network \cite{konect:massa05} and
the {\em wordnet} network \cite{konect:fellbaum98}.
All the networks are treated as undirected graphs.
When a graph is disconnected, we consider only its largest component.
Table~\ref{table:dataset} summarizes specifications of the largest components of
our real-world networks.

\subsection{Empirical Evaluation of Discriminability}
\label{sec:empiricaldiscriminability}

We measure {\em discriminability} of a centrality notion in terms of its power
in assigning distinguished values to the vertices.
Hence, for each centrality notion and over each network $G$,
we define {\em discriminability} as:
\[\frac{\#\text{distinct centrality scores}}{\#\text{vertices of }G}\times 100.\]
Among different distance-based notions studied in this paper,
we investigate discriminability of {\em discriminative closeness} centrality.
The reason is that on the one hand, notions such as
average discriminative path length and average discriminative eccentricity are graph characteristics,
rather than vertex properties.
Hence, it does not make sense to measure their discriminability.
On the other hand, closeness centrality is a much more common distance-based notion
to rank vertices than
the other distance-based notions such eccentricity.
We compare {\em discriminative closeness} centrality against {\em closeness} centrality,
as well as a number of centrality notions that are not based on distance, including
{\em betweenness} centrality \cite{DBLP:journals/cj/Chehreghani14},
{\em length-scaled betweenness} centrality \cite{Brandes08onvariants}
{\em linearly scaled betweenness} centrality \cite{Brandes08onvariants}
and {\em Katz} centrality \cite{Katz1953}\footnote{To compute betweenness centrality and its variations,
we use boost graph library (\url{http://www.boost.org/doc/libs/1_66_0/libs/graph/doc/index.html}) and
to compute Katz centrality, we use NetworKit (\url{https://networkit.iti.kit.edu/}),
where all these algorithms are implemented in C++.}.
Katz centrality has three parameters to adjust: the damping factor $\alpha$,
the bias constant $\beta$ and the convergence tolerance $tol$.
Similar to e.g., \cite{Zhan2017}, we set $\beta$ to $1$.
In order to guarantee convergence, $\alpha$ must be less than
the inverse of the largest eigenvalue of the graph.
Here we set it to $0.001$, which is one of the values used in the experiments of \cite{Zhan2017}.
We set $tol$ to $1e-10$.

Table~\ref{table:discriminability} reports the discriminability results.
In the table, a 'higher percentage' means a 'higher discriminability' of the centrality notion.
The followings can be seen in the table.
First,
{\em discriminative closeness centrality} is always more discriminative than the other indices.
Second, over datasets such as
{\em dblp0305}, {\em dblp0507}, {\em dblp9202}, {\em facebook-uniform} and {\em web-Stanford},
discriminability of discriminative closeness centrality is significantly larger than
discriminability of the other indices.
In fact, when over a network discriminability of the other indices is very low,
discriminative closeness centrality becomes significantly more discriminative than them.
However, when the other indices are discriminative enough,
the difference between discriminability of the indices is less considerable.
Third, Katz centrality is usually more discriminative than closeness centrality,
betweenness centrality, length scaled betweenness centrality and linearly scaled betweenness centrality.
The only exception is {\em web-NotreDame}, where
length scaled betweenness centrality and linearly scaled betweenness centrality are more discriminative than
Katz centrality.
However, unlike the other indices, Katz centrality uses all paths,
which makes it improper for the applications where the concept of shortest paths is essential.
Fourth, while in most cases betweenness centrality and its variations are more discriminative
than closeness centrality, in a few cases,
e.g., over {\em pics\_ut}, {\em epinions} and {\em wordnet},
closeness centrality is more discriminative than betweenness centrality and its variations.
Fifth, while length scaled and linearly scaled betweenness centrality
always show the same discriminability, they slightly improve discriminability of betweenness centrality.
However, this improvement is not considerable.

Figure~\ref{fig:time} compares running times of computing different indices.
Since betweenness centrality, length scaled betweenness centrality and linearly scaled betweenness centrality
follow exactly the same procedure and differ only in the way of aggregating the computed scores,
we report only one time for all of them.
As can be seen in the figure, since Katz centrality does not find shortest paths
and at each vertex, simply follows all its neighbors,
it is computed much faster than the other indices.
Closeness centrality is computed faster than discriminative closeness
and discriminative closeness is computed faster betweenness centrality and its variations.
Note that the algorithms of computing closeness centrality and discriminative closeness centrality
have the same time complexity.
However, to compute discriminative closeness centrality,
compared to closeness centrality
we require to perform extra operations (e.g., counting the number of shortest paths).
This makes it in practice slower than closeness centrality.

\subsection{Empirical Evaluation of Randomized Algorithms}
\label{sec:empiricalrandomized}

\begin{table*}
\caption{\label{table:adpl}
Relative error of our randomized average discriminative path length estimation algorithm.}
\centering
\begin{tabular}{l|p{1.5cm} p{1.5cm}| p{2.4cm} p{2.7cm} }
\hline \hline
\multirow{2}{*}{Database}& \multicolumn{2}{|c|}{Exact values}  & \multicolumn{2}{c}{Approximate algorithm} \\
\cline{2-5}
 & \multirow{1}{*}{APL}  & \multirow{1}{*}{ADPL} & Sample size ($\%$) & Relative error ($\%$) \\
\hline \hline
dblp0305   & $1.99997$ &  $1.99995$ & $10$ & $0.0016$\\
           & $ $ &  $ $ & $1$ & $0.0016$ \\
           & $ $ &  $ $ & $0.1$ & $0.0016$ \\
\hline
dblp0507   & $1.99997$ &  $1.99996$ & $10$ & $0.0008$ \\
           & $ $ &  $ $ & $1$ & $0.0008$ \\
           & $ $ &  $ $ & $0.1$ & $0.0008$ \\
\hline
dblp9202   & $1.99997$ &  $1.99996$ & $10$ & $0.0015$\\
           & $ $ &  $ $ & $1$ & $0.0015$\\
           & $ $ &  $ $ & $0.1$ & $0.0012$\\
\hline
facebook-uniform & $1.99998$ &  $1.99997$ & $10$ & $0.0097$ \\
           & $ $ &  $ $ & $1$ & $0.0099$  \\
           & $ $ &  $ $ & $0.1$ & $0.0102$  \\
\hline
flickr     & $ 2.3078$ &  $0.2787$ & $10$ & $2.5639$ \\
           & $ $ &  $ $ & $1$ & $0.2887$ \\
           & $ $ &  $ $ & $0.1$ & $2.7859$ \\
\hline
gottron-reuters & $ 2.9555$ &  $0.6860$ & $10$ & $0.5827$ \\
              & $ $ &  $ $ & $1$ & $3.6259$\\
              & $ $ &  $ $ & $0.1$ & $19.3603$\\
\hline
petster-friendships  & $2.7028$ &  $0.2220$ & $10$ & $0.8221$ \\
              & $ $ &  $ $ & $1$ & $0.4389$\\
              & $ $ &  $ $ & $0.1$ & $2.4948$\\
\hline
pics\_ut & $ 3.6961$ &  $0.2953$ & $10$ & $0.4478$ \\
              & &  $ $ & $1$ & $1.8667$\\
              & &  $ $ & $0.1$ & $2.9500$\\
\hline
web-Stanford  & $6.8152$ &  $0.9509$ & $10$ & $0.6261$ \\
              & $ $ &  $ $ & $1$ & $1.4910$\\
              & $ $ &  $ $ & $0.1$ & $2.7938$\\
\hline
web-NotreDame & $7.1731$ &  $1.5856$ & $10$ & $0.0618$ \\
              & $ $ &  $ $ & $1$ & $ 0.6948$\\
              & $ $ &  $ $ & $0.1$ & $2.9328$\\
\hline
citeulike-ut  & $ 3.9376$ &  $0.2361$ & $10$ & $0.0355$ \\
              & $ $ &  $ $ & $1$  & $1.6612$\\
              & $ $ &  $ $ & $0.1$  & $2.3498$\\
\hline
epinions      & $4.1814$ &  $0.9098$ & $10$ & $0.0240$ \\
              & $ $ &  $ $ & $1$  & $0.7403$\\
              & $ $ &  $ $ & $0.1$ & $0.7527$\\
\hline
wordnet       & $5.5320$ &  $1.1141$ & $10$ & $0.1610$ \\
              & $ $ &  $ $ & $1$ & $0.6710$\\
              & $ $ &  $ $ & $0.1$  & $2.7228$\\
\hline \hline
\end{tabular}
\end{table*}

Table~\ref{table:adpl} presents the results of the empirical evaluation of
our proposed randomized algorithm for estimating average discriminative path length.
When estimating average discriminative path length or average discriminative eccentricity,
we define relative error of the approximation algorithm as:
\[\frac{|\text{\em exact score} - \text{\em approximate score}|}{\text{\em exact score}}\times 100,\]
where
{\em exact score} and {\em approximate score} are respectively
the values computed by the exact and approximate algorithms.
Sample sizes are expressed in terms of the percentages of the number of vertices of the graph.
We examine the algorithm for three sample sizes:
$10\%$ of the number of vertices,
$1\%$ of the number of vertices
and $0.1\%$ of the number of vertices.
As can be seen in the table, only a very small sample size, e.g., $0.1\%$ of the number of vertices,
is sufficient to have an accurate estimation of average discriminative path length.
Over all the datasets, except {\em gottron-reuters},
this sample size gives a relative error less than $3\%$.
In particular, relative error in the datasets
{\em dblp0305}, {\em dblp0507}, {\em dblp9202} and {\em facebook-uniform}
is very low.
This is consistent with our analysis presented in Section~\ref{sec:randomized}
and is due to very small discriminative diameter of these networks.

Table~\ref{table:adpl} also compares
average discriminative path length of the networks with their average path length.
For all the datasets, except {\em dblp0305}, {\em dblp0507}, {\em dblp9202} and {\em facebook-uniform},
average discriminative path length is considerably smaller than average path length.
It may seem surprising that despite very high discriminability of {\em discriminative closeness}
compared to {\em closeness} over {\em dblp0305}, {\em dblp0507}, {\em dblp9202} and {\em facebook-uniform},
the differences between {\em average discriminative path length} and {\em average path length} are tiny.
The reason is that over these datasets,
on the one hand, between a huge number of pairs of vertices there is only one shortest path;
a few pairs have two shortest paths and only a very tiny percentage of pairs have three or more shortest paths.
Therefore, those pairs that have more than one shortest paths do not have a considerable contribution
to $ADPL$, hence, $ADPL$ and $APL$ find very close values.
However, on the other hand,
for each vertex $v$ there are a different number of vertices to which $v$ is connected by
two or more shortest paths.
This is sufficient to distinguish its discriminative closeness from the other vertices.

Table~\ref{table:ade} reports the results of the empirical evaluation of
our randomized algorithm for estimating average discriminative eccentricity.
Similar to the case of average discriminative path length,
we test the algorithm for three different sample sizes and our experiments
show that only a small sample size, e.g., $0.1\%$ of the number of vertices,
can yield a very accurate estimation of average discriminative eccentricity.
In our experiments, for the sample size $0.1\%$, relative error is always less than $5\%$.
This high accuracy is due to very small {\em discriminative diameter} of the networks.
Similar to the case of {\em average eccentricity}
where a simple randomized algorithm significantly
outperforms advanced techniques \cite{Shun:2015:EPE:2783258.2783333},
our simple algorithms show very good efficiency and accuracy
for estimating average
discriminative path length and average discriminative eccentricity.
Table~\ref{table:ade} also shows that
similar to $ADPL$,
while the datasets {\em dblp0305}, {\em dblp0507}, {\em dblp9202} and {\em facebook-uniform}
have (almost) the same values for $AE$ and $ADE$,
over the rest of the datasets $ADE$ is less than $AE$.

\begin{table*}
\caption{\label{table:ade}
Relative error of our randomized average discriminative eccentricity estimation algorithm.}
\centering
\begin{tabular}{l| l l | p{2.4cm} p{2.7cm} }
\hline \hline
\multirow{2}{*}{Database}& \multicolumn{2}{|c|}{Exact values}  & \multicolumn{2}{c}{Approximate algorithm} \\
\cline{2-5}
 & \multirow{1}{*}{AE ($\times 1000$)} & \multirow{1}{*}{ADE ($\times 1000$)} & Sample size ($\%$) & Relative error ($\%$)\\
\hline \hline
dblp0305    & $0.0183$ & $0.0183$ & $10$  & $0.0013$\\
            & $ $ &  $ $ & $1$  & $0.0013$ \\
            & $ $ &  $ $ & $0.1$ & $0.0013$ \\
\hline
dblp0507    & $0.0148$ &  $0.0148$ & $10$  & $0.0007$\\
            & $ $ &  $ $ & $1$  & $0.0007$ \\
            & $ $ &  $ $ & $0.1$ & $0.0007$ \\
\hline
dblp9202    & $0.0154$ &  $0.0154$ & $10$  & $0.0015$\\
            & $ $ &  $ $ & $1$  & $0.0015$ \\
            & $ $ &  $ $ & $0.1$ & $0.0015$ \\
\hline
facebook-uniform  & $0.0148$ &  $0.0148$ & $10$  & $0.0096$\\
            & $ $ &  $ $ & $1$  & $0.0096$ \\
            & $ $ &  $ $ & $0.1$ & $0.0096$ \\
\hline
flickr      & $0.0566$ &  $0.0323$ & $10$  & $0.2627$\\
            & $ $ &  $ $ & $1$  & $1.1411$ \\
            & $ $ &  $ $ & $0.1$ & $1.6568$ \\
\hline
gottron-reuters   & $0.1159$ &  $0.0898$ & $10$  & $0.2327$\\
            & $ $ &  $ $ & $1$  & $0.4596$ \\
            & $ $ &  $ $ & $0.1$ & $4.4685$ \\
\hline
petster-friendships  & $0.0432$ &  $0.0293$ & $10$  & $0.0749$\\
            & $ $ &  $ $ & $1$  & $0.04465$ \\
            & $ $ &  $ $ & $0.1$ & $2.3459$ \\
\hline
pics\_ut    & $0.0636$ &  $0.0450$ & $10$  & $0.0604$\\
            & $ $ &  $ $ & $1$  & $0.7933$ \\
            & $ $ &  $ $ & $0.1$ & $0.8762$ \\
            \hline
web-Stanford  & $0.4171$ &  $0.0314$ & $10$  & $0.3697$\\
              & $ $ &  $ $ & $1$  & $1.0153$ \\
              & $ $ &  $ $ & $0.1$ & $2.4259$ \\
\hline
web-NotreDame  & $0.0852$ &  $0.0399$ & $10$  & $0.0235$\\
               & $ $ &  $ $ & $1$  & $0.4150$ \\
               & $ $ &  $ $ & $0.1$ & $0.4150$ \\
\hline
citeulike-ut   & $0.0406$ &  $0.0262$ & $10$  & $0.3076$\\
            & $ $ &  $ $ & $1$  & $0.2016$ \\
            & $ $ &  $ $ & $0.1$ & $3.2315$ \\
\hline
epinions    & $0.0894$ &  $0.0676$ & $10$  & $0.0780$\\
            & $ $ &  $ $ & $1$  &  $0.2170$ \\
            & $ $ &  $ $ & $0.1$ & $0.3784$ \\
\hline
wordnet     & $0.0780$ &  $0.0589$ & $10$  & $0.0724$\\
            & $ $ &  $ $ & $1$  &  $0.4879$ \\
            & $ $ &  $ $ & $0.1$ & $0.5011$ \\
\hline \hline
\end{tabular}
\end{table*}

\subsection{The Tiny-World Property}
\label{sec:tinyworld}

It is well-known that in real-world networks,
{\em average path length} is
proportional to the logarithm of the number of vertices in the graph and it is
considerably smaller than the {\em largest distance} that two vertices may have in a graph \cite{watts1998cds}.
Our extensive experiments presented in Table~\ref{table:adpl}
reveal that
in real-world networks
{\em average discriminative path length} is
much more smaller than the {\em largest discriminative distance}\footnote{Both
the {\em largest distance} and the {\em largest discriminative distance} that two vertices may have in a graph are equal to
the number of vertices in the graph minus 1.}
that two vertices may have in a graph
and it is bounded by a constant (i.e., $2$).
This also implies that {\em average discriminative path length} of a network
is usually considerably smaller than its {\em average path length}.

This property means that in real-world networks,
not only most vertices can be reached from every other vertex by a small number of steps,
but also there are many different ways to do so.
We call this property the {\em tiny-world} property.
A consequence of this property is that
removing several vertices from a real-world network
does not have a considerable effect on its {\em average path length}.
Note that this property does not contradict the high discriminability of discriminative closeness;
while this property implies that vertices in average have a tiny discriminative distance from each other,
the high discriminability of discriminative closeness implies that
the discriminative closeness scores of different vertices are less identical than their closeness scores.
In Table~\ref{table:adpl},
it can be seen that networks such as {\em flickr}, {\em petster-friendships}, {\em pics\_ut} and {\em citeulike-ut}
have an average discriminative path length considerably smaller than the others.
This is due to the high density of these networks,
which yields that any two vertices may have a shorter distance or more shortest paths.

\section{Link prediction}
\label{sec:linkprediction}

In order to better motivate the applicability and usefulness of our proposed
distance measure,
in this section we present a novel {\em link prediction} method,
which is based on our new distance measure.
We empirically evaluate our method and
show that it outperforms the well-known existing link prediction methods.

In the link prediction problem studied in this paper,
we are given an unweighted and undirected graph $G$ in which each
 edge $e = \{u,v\}$ has a timestamp.
For a time $t$,
let $G[t]$ denote the subgraph of $G$ consisting of all edges
with a timestamp less than or equal to $t$.
Then the link prediction task is defined as follows.
Given network $G[t]$ and a time $t'>t$,
(partially) sort the list of all pairs of vertices that are not connected in $G[t]$,
according to their probability (likelihood)
of being connected during the interval $(t,t']$.
We refer to the intervals $[0,t]$ and $(t,t']$ as the {\em training interval} and
the {\em test interval}, respectively.

To generate this (decreasingly) sorted list,
existing methods
during the training interval
compute a similarity matrix $S$
whose entry $S_{uv}$ is the score (probability/likelihood) of having an edge between vertices $u$ and $v$.
Generally, $S$ is symmetric, i.e., $S_{uv} = S_{vu}$.
The pairs of the vertices that are at the top of the ordered list are
most likely to be connected during the test interval \cite{Martinez:2016:SLP:3022634.3012704}.
To compute $S_{u,v}$, several methods have been proposed in the literature,
including
{\em the number of common neighbors} \cite{newman2001clustering},
{\em negative of shortest path length} \cite{Liben-Nowell:2007:LPS:1241540.1241551}
and its variations \cite{DBLP:conf/bncod/LebedevLRM17},
the {\em Jaccard's coefficient} \cite{Salton:1986:IMI:576628},
the {\em preferential attachment index} \cite{RePEc:eee:phsmap:v:311:y:2002:i:3:p:590-614},
{\em hitting time} \cite{Liben-Nowell:2007:LPS:1241540.1241551},
{\em SimRank} \cite{Jeh:2002:SMS:775047.775126},
{\em Katz index} \cite{Katz1953},
the {\em Adamic/Adar index} \cite{adamic2003friends}
and {\em resource allocation based on common neighbor interactions} \cite{Zhang2014}.
In the literature, there are also many algorithms that exploit a classification algorithm,
with these indices as the features,
and try to predict whether a pair of unconnected vertices will be connected
during the test interval or not \cite{LU20111150,Hasan06linkprediction,Martinez:2016:SLP:3022634.3012704}.

\begin{table*}
\caption{\label{table:dataset2}Specifications of the temporal real-world datasets used in
our experiments for link prediction.}
\begin{center}
\begin{tabular}{ l | p{7.5cm} l p{2cm} l }
\hline
Dataset & Link & \#vertices & \#temporal edges & Time span \\
\hline
sx-stackoverflow   & \url{https://snap.stanford.edu/data/sx-stackoverflow.html} & 2,601,977&63,497,050 & 2774 days \\
sx-mathoverflow    & \url{http://snap.stanford.edu/data/sx-mathoverflow.html} & 24,818  & 506,550     & 2350 days \\
sx-superuser       & \url{https://snap.stanford.edu/data/sx-superuser.html} & 194,085 & 1,443,339   & 2773 days \\
sx-askubuntu       & \url{http://snap.stanford.edu/data/sx-askubuntu.html} & 159,316   & 964,437 & 2613 days \\
wiki-talk-temporal & \url{https://snap.stanford.edu/data/wiki-talk-temporal.html}&1,140,149 & 7,833,140& 2320 days \\
CollegeMsg         & \url{http://snap.stanford.edu/data/CollegeMsg.html} & 1,899     & 20,296      & 193 days  \\
\hline
\end{tabular}
\end{center}
\end{table*}

In this section, we propose a new method,
called \textsf{LIDIN}\footnote{\textsf{LIDIN} is an abbreviation
for \textbf{LI}nk prediction based on \textbf{DI}stance and the \textbf{N}mber of shortest paths.},
for sorting the list of
pairs of unconnected vertices, which is a combination of {\em shortest path length}
and {\em discriminative distance}.
For two pairs of unconnected vertices $\{u_1,v_1\}$ and $\{u_2,v_2\}$,
using \textsf{LIDIN} we say
vertices $u_2$ and $v_2$ are more likely to form a link during the test interval
than vertices $u_1$ and $v_1$ if:
\begin{itemize}
\item
$d(u_1,v_1)>d(u_2,v_2)$, or
\item
$d(u_1,v_1)=d(u_2,v_2)$ and $dd(u_1,v_1)>dd(u_2,v_2)$.
\end{itemize}
The rationale behind \textsf{LIDIN} is that
when comparing a pair of vertices $u_1,v_1$ with another pair $u_2,v_2$,
if $d(u_1,v_1)=d(u_2,v_2)$ but $u_2$ and $v_2$ are connected to each other by
more shortest paths than $u_1$ and $v_1$,
then they are more likely to form a link during the test interval.
As a special case, for a fixed $k$, consider the list $L(k)$
consisting of all pairs of unconnected vertices $u$ and $v$
such that $d(u,v)=k$.
A network may have many such pairs.
It is known that compared to the pairs of unconnected vertices that have distance $k+1$,
members of $L(k)$ are more likely
to form a link during the test
interval \cite{Pasta2014,DBLP:conf/uai/ChehreghaniC16}.
However, the question remaining open is
what elements of $L(k)$ are more likely to be connected than the other members?
Using \textsf{LIDIN}, we argue that by increasing the number of shortest paths between the two vertices,
the probability of forming a link increases, too.

In order to empirically evaluate this argument,
we perform tests over several {\em temporal} real-world networks, including
sx-stackoverflow \cite{DBLP:conf/wsdm/ParanjapeBL17},
sx-mathoverflow \cite{DBLP:conf/wsdm/ParanjapeBL17},
sx-superuser \cite{DBLP:conf/wsdm/ParanjapeBL17},
sx-askubuntu \cite{DBLP:conf/wsdm/ParanjapeBL17},
wiki-talk-temporal \cite{DBLP:conf/wsdm/ParanjapeBL17,leskovec2010} and
CollegeMsg \cite{DBLP:journals/jasis/PanzarasaOC09}.
Table~\ref{table:dataset2} summarizes
the specifications of the used temporal real-world datasets.
We consider all these networks as simple and undirected graphs,
where multi-edges and self-loops are ignored.
Since the networks
sx-stackoverflow, sx-superuser, sx-askubuntu and wiki-talk-temporal
are too large to load their unconnected pairs of vertices in the memory,
after sorting their edges based on timestamp,
we only consider the subgraphs generated by their first 300,000 edges.

\begin{figure*}
\centering
\subfigure[sx-stackoverflow]
{
\includegraphics[scale=0.41]{sx-stackoverflow_auc}
\label{fig:sx-stackoverflow_auc}
}
\subfigure[sx-mathoverflow]
{
\includegraphics[scale=0.41]{sx-mathoverflow_auc}
\label{fig:sx-mathoverflow_auc}
}
\subfigure[sx-superuser]
{
\includegraphics[scale=0.41]{sx-superuser_auc}
\label{fig:sx-superuser_auc}
}
\subfigure[sx-askubuntu]
{
\includegraphics[scale=0.41]{sx-askubuntu_auc}
\label{fig:sx-askubuntu_auc}
}
\subfigure[wiki-talk-temporal]
{
\includegraphics[scale=0.41]{wiki-talk-temporal_auc}
\label{fig:wiki-talk-temporal_auc}
}
\subfigure[CollegeMsg]
{
\includegraphics[scale=0.41]{CollegeMsg_auc}
\label{fig:CollegeMsg_auc}
}
\caption
{
$AUC$ of different link prediction algorithms.
{\em Ratio} shows the percentage of the edges that form the training interval.
\label{figure:auc}
}
\end{figure*}

\begin{figure*}
\centering
\subfigure[sx-stackoverflow]
{
\includegraphics[scale=0.41]{sx-stackoverflow_Q}
\label{fig:sx-stackoverflow_Q}
}
\subfigure[sx-mathoverflow]
{
\includegraphics[scale=0.41]{sx-mathoverflow_Q}
\label{fig:sx-mathoverflow_Q}
}
\subfigure[sx-superuser]
{
\includegraphics[scale=0.41]{sx-superuser_Q}
\label{fig:sx-superuser_Q}
}
\subfigure[sx-askubuntu]
{
\includegraphics[scale=0.41]{sx-askubuntu_Q}
\label{fig:sx-askubuntu_Q}
}
\subfigure[wiki-talk-temporal]
{
\includegraphics[scale=0.41]{wiki-talk-temporal_Q}
\label{fig:wiki-talk-temporal_Q}
}
\subfigure[CollegeMsg]
{
\includegraphics[scale=0.41]{CollegeMsg_Q}
\label{fig:CollegeMsg_Q}
}
\caption
{
The value of $Q$ for different link prediction algorithms.
{\em Ratio} shows the percentage of the edges that form the training interval.
\label{figure:q}
}
\end{figure*}

We compare \textsf{LIDIN} with
{\em negative of shortest path length} \cite{Liben-Nowell:2007:LPS:1241540.1241551}
and the {\em Adamic/Adar index} \cite{adamic2003friends},
denoted respectively by \textsf{-SPL} and \textsf{AA}.
We choose \textsf{-SPL} because \textsf{LIDIN} is inherently an improvement of \textsf{-SPL},
furthermore, the experiments reported in \cite{Hasan06linkprediction}
show that this index outperforms the other topological (global) indices studied in that paper.
We choose \textsf{AA} because the experiments reported in \cite{Liben-Nowell:2007:LPS:1241540.1241551}
show that among $11$ studied indices,
the Adamic/Adar index has the best relative performance ratio
versus random predictions,
the best relative performance ratio versus negative of shortest path length predictor and
the best relative performance ratio versus common neighbors predictor\footnote{We can use these
indices either as the features of a classification algorithm
(like e.g., \cite{Hasan06linkprediction}),
or as the criteria of sorting the list of unconnected pairs of vertices
(like e.g., \cite{Liben-Nowell:2007:LPS:1241540.1241551}).
Here,
since we want to omit the effect of the classification algorithm
and study only the effect
of our new notion, we follow the second option.}.

For the graph formed during training interval,
we sort (increasingly when \textsf{LIDIN} is used and
decreasingly when \textsf{-SPL} and \textsf{AA} are used)
the list $L$
of all pairs of unconnected vertices,
based on each of the indices\footnote{
When any of these indices is used,
there might exist two or more pairs
that are not sorted by the index.
In this case, these pairs are sorted according to the identifiers of the end-points of the edges.}.
Then, during the test interval, for each edge that connects a pair in $L$, we examine its rank in $L$.
In order to evaluate the accuracy of a link prediction method,
we use two measures {\em area under the ROC curve} ($AUC$) and {\em ranking error} ($Q$).
In $AUC$,
we measure the probability that a randomly chosen pair of vertices that find a link
during the test interval have a higher score than
a randomly chosen pair of vertices that do not find a link
during the test interval.
Formally,
$AUC$ of a method $ind$ is defined as \cite{aucnature}:
\[AUC(ind) = \frac{n_g+0.5n_e}{n_t},\]
where $n_t$ is the number of times that we randomly choose two pairs of
vertices; one from those that form a link during the test  interval and the other from those that do not;
$n_g$ is the number of times that the one that forms a link gets a higher score than the other,
and $n_e$ is the number of times that the scores of the two chosen pairs are equal.
A higher value of $AUC$ implies a better link prediction method.
In our experiments,
we set $n_t$ to the number of edges in the test interval divided by $10$.
However, similar results can be seen for other values of $n_t$.

We define the {\em ranking error} of a method $ind$ as:
\[Q(ind) = \sum_{\{u,v\} \in TE} \frac{rank(\{u,v\},L_{ind})}{|TE|},\]
where
$L_{ind}$ is the list $L$ sorted according to $ind$,
$TE$ contains those edges of the test interval that connect a pair in $L$,
and $rank(\{u,v\},L_{ind})$ returns the rank of $\{u,v\}$ in $L_{ind}$.
For two given indices $ind1$ and $ind2$,
$Q(ind1) < Q(ind2)$ means that compared to $ind2$,
$ind1$ gives more priority (i.e., a better rank) to the pairs that
form a link during the test interval, hence,
$ind1$ is a better method than $ind2$.

We sort the edges of each network according to their timestamps
and form the training and test intervals based on the timestamps,
i.e., for some given value $\tau$,
training interval contains those edges that have a timestamp at most $\tau$
and test interval contains those edges that have a timestamp larger than $\tau$.
A factor that may affect the empirical behavior of the indices is the value of $\tau$.
Therefore and to examine this,
we consider 4 different settings for each network,
and choose the values of $\tau$ in such a way that training interval includes
$60\%$, $70\%$, $80\%$ and $90\%$ of the edges.
In each case, the rest of the edges which are between a pair of vertices unconnected in the training interval,
belong to the test interval.

Figure~\ref{figure:auc} compares $AUC$ of different methods.
Over all the datasets and in all the settings,
\textsf{LIDIN} has the highest $AUC$, therefore,
it has the best performance.
Figure~\ref{figure:q} reports the $Q$ of the studied methods over different datasets.
As can be seen in the figure, in all the cases,
\textsf{LIDIN} has the lowest $Q$ and hence, the best performance.
These tests empirically verify our above mentioned argument
that among all the pairs of unconnected vertices in $L(k)$,
those that have a smaller {\em discriminative distance} (and hence, are closer!),
are more likely to form a link.
While in most cases \textsf{-SPL} outperforms \textsf{AA},
over {\em sx-mathoverflow} and for all values of {\em ratio},
\textsf{AA} has a higher $AUC$ and a lower $Q$ than \textsf{-SPL}.
The superior performance of our proposed link prediction method suggests that
the {\em inverse of discriminative distance} might be useful
in determining similarity between vertices of a network.
This means, for example, more than using the fixed criteria for determining the similarity of objects
in a Social Internet of Vehicle (SIoV) \cite{8070948}
or friendship of User Equipments \cite{8119808},
someone may also use the inverse of discriminative distance.

\section{Conclusion and future work}
\label{sec:conclusion}

In this paper,
we proposed a new distance measure between vertices of a graph,
which is proportional to the length of shortest paths and
inversely proportional to the number of shortest paths.
We presented exact and randomized algorithms
for computation of the proposed discriminative indices and analyzed them.
Then, by performing extensive experiments over several real-world networks,
we first showed that compared to the traditional indices,
discriminative indices have usually much more discriminability.
We then showed that our randomized algorithms can very precisely estimate average discriminative path length and
average discriminative eccentricity,
using only a few samples.
In the end, we presented a novel link
prediction method, that uses discriminative distance to decide which
vertices are more likely to form a link in future, and showed its superior
performance compared to the well-known existing measures.

The current work can be extended in several directions.
An interesting direction is to investigate distribution of discriminative closeness and
discriminative vertex eccentricity in large networks.
In particular, it is useful to see whether there exist correlations
among discriminative indices on the one hand
and other centrality indices such as betweenness and degree on the other hand.
The other direction for future work is to develop efficient randomized algorithms
for estimating discriminative closeness and discriminative eccentricity
of one vertex or a set of vertices and discriminative diameter of the graph.
For example, it is interesting to develop algorithms similar
to \cite{DBLP:conf/alenex/BergaminiBCMM16} that estimate
$k$ highest discriminative closeness scores in the graph.
The other extension of the current work is
the empirical evaluation of the generalizations of the discriminative indices
presented in Section~\ref{sec:discriminativecloseness}.
Finally, another extension of the current work is to study discriminative indices
of different {\em network models} \cite{HAGHIRCHEHREGHANI20171}.

\section*{Acknowledgement}
This work has been supported by the ANR project IDOLE.

redpajama_set_name: RedPajamaArXiv


text:
Q: Calculating power for a survey to compare different metrics I am currently planning a survey. The data will be used to test which of three metrics best captures some "true" underlying characteristic of the respondents. Getting data on the "true" underlying characteristic is costly, so I want a simplified metric that best approximates the "true" measure.
For the current survey, I am gathering four data points for each observation.
1) metric 1
2) metric 2
3) metric 3
4) the "true" underlying characteristic
In the future, I won't have data on the "true" characteristic, so I will rely on one metric. For future work we will collect just the data for the "best" metric.
I am not clear about what effect size (aka difference in prevalence of indicator) to use to calculate sample size. Specifically, the hypothesized effect that I seek to identify, I believe is the difference between the metrics in their correlation to the true measure. For instance, if metric 1 has correlation 0.7 with the true characteristic, and metric 2 has a correlation 0.9, then the "effect size" of switching from metric 1 to metric 2 is 0.2.
Am I on track?

redpajama_set_name: RedPajamaStackExchange


These boats are operated by Richard and Jules, and trade under the "Jules Fuels" banner. They are based at Stoke Bruerne on the Grand Union Canal, and cover the Grand Union Canal from Stockton through Leighton Buzzard and Marsworth to Apsley, together with the North Oxford Canal from Braunston to Hillmorton.
They regularly come up to Awbridge to load solid fuel from our yard, and often arrive with Southern Cross and Stanton to load up too.
Towcester first appeared at Awbridge in 2007 to load coal on behalf of Mike Partridge. Jules and Richard enjoyed the experience so much that they subsequently purchased the business from Mike and have been regular visitors to Awbridge ever since.
They have their own website - click here to access it.


text:
Home Grown Players (HGP) Quota – January 2021 Transfer Window
I tend to write each year about the 25-man squad and the implications of the home grown players rule and how it will impact on Spurs' transfer strategy. The home grown player numbers could impact on how many signings José Mourinho can make, the nature of those signings and/or the size of our squad for the rest of the season.
The Premier League 'Home Grown Players (HGP)' Rule
The misconception about the requirement itself is that clubs must name eight home grown players in their squads. We could name fewer than eight HGPs, but would need to also name fewer than 25 players in our squad — for example, if we only have seven HGPs, we can name a 24-man squad, 6/23, 5/22, etc.
Remember, an HGP is defined as one whom, irrespective of nationality or age, has been registered with any club affiliated to The Football Association or the Football Association of Wales for a period, continuous or not, of three entire seasons, or 36 months, before his 21st birthday (or the end of the season during which he turns 21). Source: Premier League.
As ever, we will not need to name players who are under 21 on our squad list, so could augment our squad with youngsters. This would mean that we could manage with, say, a 22-man squad with just five HGPs, but would need plenty of under 21 players who are ready to play (particularly if we qualify for the Europa League). For the 2020/21 campaign, players considered 'under 21' will have been born on or after 1st January 1999. This means that for the current season we still have a number of 'freebies' who are fairly well-known names: Brandon Austin, Gedson Fernandes (if he stays…), Japhet Tanganga, Jack Clarke, Jamie Bowden, Harvey White, J'Neil Bennett, Malachi Fagan-Walcott, Dennis Cirkin.
Remember, we also have some players out on-loan – these players could also have been classified as 'freebies': Jack Roles, TJ Eyoma, Ryan Sessegnon, Oliver Skipp, Troy Parrott. More players may well move out on loan in January.
The Europa League 'Home Grown Players (HGP)' Rule
The Europa League rules are a little different to the Premier League rules — have a look at article 42 ('Player lists') of the regulations. UEFA don't just want clubs to have players trained elsewhere in the FA structure — they have additional requirements for club-trained players. They want to encourage clubs to bring through their own young players.
If we want to name a 'full' squad in the Europa League, we would need at least four 'association-trained' players (we currently have: Hart, Dele, Doherty, Sessegnon, Clarke) and four 'club-trained' players (we currently have: Bale, Georgiou, Kane, Marsh, Rose, Sterling, Tracey, Whiteman and Winks). Many of these players are on-loan (Sessegnon, Sterling, Tracey), or simply not likely to be selected (Georgiou, Marsh, Rose).
When we named our Premier League squad list in October, we included exactly 25 players, nine of whom were HGP: Dele Alli, Gareth Bale, Ben Davies, Matt Doherty, Joe Hart, Harry Kane, Joe Rodon, Alfie Whiteman, Harry Winks. If we were to sell or loan Dele or Winks, we would would be able to add one additional HGP or non-HGP without removing any other players from the squad list. If we were to sell or loan both, we would only be able to name a 24-man squad unless we signed a new HGP.
It's a more delicate situation in the Europa League, though. The bottom line is that, if we were to sell or loan Dele and/or Winks, our Europa League squad would be reduced. We could replace Dele with another association-trained player were we to sign someone new, but we could only replace Winks with a club-trained player (Georgiou, Marsh, Rose, Sterling, Tracey). Of course, we could also sign a non-locally trained player and remove another from the Europa League squad.
# Player DOB Age Status PL HGP EL Locally Trained
1 Hugo Lloris 26/12/1986 34
2 Joe Hart 19/04/1987 33 Y Association
3 Toby Alderweireld 02/03/1989 31
4 Gareth Bale 16/07/1989 31 Y Club
5 Moussa Sissoko 16/08/1989 31
6 Danny Rose 02/07/1990 30 Y Club
7 Paulo Gazzaniga 02/01/1992 28
8 Matt Doherty 16/02/1992 28 Y Association
9 Erik Lamela 04/03/1992 28
10 Son Heung-min 08/07/1992 28
11 Lucas Moura 13/08/1992 28
12 Serge Aurier 24/12/1992 28
13 Ben Davies 24/04/1993 27 Y
14 Harry Kane 28/07/1993 27 Y Club
15 Eric Dier 15/01/1994 26
16 Pierre-Emile Højbjerg 05/08/1995 25
17 Harry Winks 02/02/1996 24 Y Club
18 Giovani Lo Celso 09/04/1996 24
19 Dele Alli 11/04/1996 24 Y Association
20 Davinson Sánchez 12/06/1996 24
21 Sergio Reguilón 16/12/1996 24
22 Tanguy Ndombele 28/12/1996 24
23 Anthony Georgiou 24/02/1997 23 Y Club
24 Steven Bergwijn 08/10/1997 23
25 Joe Rodon 22/10/1997 23 Y
26 Cameron Carter-Vickers 31/12/1997 22 On-loan Y Club
27 Juan Foyth 12/01/1998 22 On-loan
28 Shilow Tracey 29/04/1998 22 On-loan Y Club
29 Alfie Whiteman 02/10/1998 22 Y Club
30 George Marsh 05/11/1998 22 Y Club
31 Kazaiah Sterling 09/11/1998 22 On-loan Y Club
32 Gedson Fernandes 09/01/1999 21 N/A
33 Ryan Sessegnon 18/05/2000 20 On-loan N/A Association
34 Jack Clarke 23/11/2000 20 N/A Association
Spurs' over-21 (and UEFA List A under-21) players, ordered by DOB
I recently added a Donate button to this site. It's on the 'About' page. I explain why on there. Cheers!
ReplyCancel reply
© 2021 WindyCOYS


text:
Guest Post: Should Corruption Prosecutors Tweet? The Brazilian Example
Posted on July 26, 2018 by Matthew Stephenson
Today's guest post is from Victor Rodrigues, a researcher at the FGV School of Law in Rio de Janeiro, Brazil:
How openly should prosecutors investigating corruption or other high-level wrongdoing be about their activities and their views on the larger public policy questions that their investigations implicate? As has been discussed on this blog before, there is a longstanding debate on this issue, and considerable variation across countries. The United States represents one approach, in which federal prosecutors are exceedingly discreet and tight-lipped. Consider the fact that Special Counsel Robert Mueller, leading the high-profile investigation into possible wrongdoing by the Trump campaign, barely speaks in public.
Brazil seems to be going in a different direction. Not only does the Brazilian Public Prosecutor's Office have verified accounts on Facebook and Twitter, but many of the individual prosecutors are also active on social media. Perhaps the most prominent example in Brazil is Deltan Dallagnol, the federal prosecutor coordinating the Car Wash Investigation (Lava Jato). Mr. Dallagnol has used his verified account to tweet over seven thousand times, and many of his posts mention Lava Jato cases.
While we can't know for sure what impact these tweets have had, it's unlikely that an account with almost half a million followers would have no impact at all. I imagine that for many readers, for example, those from the United States or countries with similar traditions regarding prosecutorial (non-)communication with the public, Mr. Dallagnol's Twitter presence might be disconcerting, perhaps troubling. But in the context of a country like Brazil, these tweets, and prosecutorial openness more generally, are likely to have a positive impact not only on specific corruption cases but also on the development of legal and democratic institutions. In particular, this widespread use of social media by Lava Jato prosecutors can have three beneficial effects:
First, these tweets can serve educational purposes. Unlike the United States, Brazilian democracy is relatively young. Indeed, barely more than a generation has passed since Brazilians were living under a military dictatorship. As a result, most citizens may not know how government institutions work, and what their limits are—a problem exacerbated by the fact that most Brazilian schools do not teach about the current law, political institutions, or basic civics. When Mr. Dallagnol tweets about a decision in one of his cases, he usually explains what is at stake, who has the decision power, and when and how that decisionmaker is supposed to reach a decision. In doing so, he provides his followers, many of whom never really understood how the judicial system worked, with an opportunity to connect with what is happening inside the government.
Second, prosecutors' use of social media to connect with the mass public can help protect the prosecutors' autonomy. When prosecutors or others fight systemic corruption, it is to be expected that many forces will try to hinder their work. In many countries around the world, we have seen that strong public support for the anticorruption investigators and prosecutors can be crucial to protecting them against interference. The fact that Mr. Dallagnol has half a million followers, and can use his social media presence to raise awareness when, for example, the National Congress tries to undermine anticorruption efforts. His social media presence helps protect his autonomy.
Third, prosecutorial tweeting can help raise awareness of the need to address institutional deficiencies in the judiciary that impede the timely resolution of corruption cases. Sometimes the Brazilian judiciary takes more than a decade to decide a case, and every time this happens, there's a risk that the statute of limitations on the crime could expire. Tweeting the state of those cases to many Brazilian citizens could be a cost-efficient way of keeping the population aware of what is happening, and citizen attention can in turn help keep the judiciary in check. There's some evidence that some of the recent Lava Jato cases have indeed moved much faster than is typical: For example, the Court of Appeals resolved former President Lula's case in 154 days, and the same court resolved only two other public corruption cases in under 150 days. While we can't necessarily attribute this unusual speed directly to Mr. Dallagnol's tweets, the more general point is that calling public attention to the slow pace of justice may have salutary effects.
Of course, prosecutorial presence on social media has risks. Excessive openness about strategy or evidence could jeopardize the whole investigation. And if prosecutors seem overly political, this could undermine their credibility and legitimacy. Indeed, some in Brazil are already complaining that the Car Wash investigation is becoming too politicized. Yet on the whole, at least in a country like Brazil, there are distinct and considerable benefits when prosecutors responsible for investigating high-level corruption take advantage of social media to provide information and to participate in more general public discussions about how to move forward with the fight against corruption.
This entry was posted in Guest Commentary and tagged Brazil, Deltan Dallagnol, Facebook, Lava Jato, Operation Car Wash, prosecutors, social media, transparency, Twitter, Victor Rodrigues by Matthew Stephenson. Bookmark the permalink.
2 thoughts on "Guest Post: Should Corruption Prosecutors Tweet? The Brazilian Example"
Pingback: Guest Post: Should Corruption Prosecutors Tweet? The Brazilian Example – Matthews' Blog
Mauro Messias on April 8, 2019 at 1:09 pm said:
Great post, Victor Rodrigues! I agree with you that wide-spreading through social media a high-level corruption case can provide some benefits to the public in general.
However, I must point out this: even if a public disclosure of a corruption case might (1) provide educational process regarding how government institutions work, (2) increase the prosecutor's autonomy and (3) help raise awareness of the need to address institutional deficiencies in the judiciary, I believe that the social media disclosure of mere investigations should be strongly avoided, unlike the content of charges filed in court, which admits some kind of exposure.