Social Media Mining: An Introduction

P1: qVa Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-03 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:45

78 Network Measures

words, hubs represent webpages that contain many useful links to authorities

and authorities are influential nodes in the webgraph. HITS employs an

iterative approach to compute authority and hub scores for all nodes in the

graph. Nodes with high authority scores are classified as authorities and

nodes with high hub scores as hubs. Webpage with high authority scores or

hub scores can be recommended to users in a web search engine.

Betweenness algorithms can be improved using all-pair shortest paths

algorithms [Warshall, 1962] or algorithms optimized for computing

betweenness, such as the Brandes’ algorithm discussed in [Brandes, 2001;

Tang and Liu, 2010].

A review of node similarity and normalization procedures is provided in

Leicht, Holme, and Newman [2005]. Jaccard similarity was introduced in

[Jaccard, 1901] and cosine similarity is introduced bySalton and McGill

[1986].

REGE [White, 1980, 1984 ] and CATREGE [Stephen and Martin, 1993]

are well-known algorithms for computing regular equivalence.

3.7 Exercises

Centrality

1. Come up with an example of a directed connected graph in which
   eigenvector centrality becomes zero for some nodes. Describe when
   this happens.


2. Doesβhave any effect on the order of centralities? In other words,
   if for one value ofβthe centrality value of nodeviis greater than
   that ofvj, is it possible to changeβin a way such thatvj’s centrality
   becomes larger than that ofvi’s?


3. In PageRank, whatαvalues can we select to guarantee that centrality
   values are calculated correctly (i.e., values do not diverge)?


4. Calculate PageRank values for this graph when

v 1

v 2 v 3

v 4