Social Network Analysis & PageRank, HITS

Social Network Analysis

These two weeks, we have learned an effective method to find the pattern of interaction between actors in a social network, named social network analysis.

Social network analysis is the mapping and measuring of relationships and flows between people, groups, organizations, computers, URLs, and other connected information/knowledge entities. The nodes in the network are the people and groups while the links show relationships or flows between the nodes. SNA provides both a visual and a mathematical analysis of human relationships. To understand networks and their participants, we evaluate the location of actors in the network. Measuring the network location is finding the centrality of a node. These measures give us insight into the various roles and groupings in a network -- who are the connectors, mavens, leaders, bridges, isolates, where are the clusters and who is in them, who is in the core of the network, and who is on the periphery.

Two core notions in network analysis are centrality and prestige—as we will see, both are used in the link analysis for the Web. Informally, a node (or page or actor or resource) is central if it is involved in many links.

To have an actual understanding of the different categories of centrality, we see a sociogram first:

We look at a social network -- the "Kite Network" above -- developed by David Krackhardt, a leading researcher in social networks. Two nodes are connected if they regularly talk to each other, or interact in some way. Andre regularly interacts with Carol, but not with Ike. Therefore Andre and Carol are connected, but there is no link drawn between Andre and Ike. This network effectively shows the distinction between the three most popular individual centrality measures: Degree Centrality, Betweenness Centrality, and Closeness Centrality.

Degree Centrality: Social network researchers measure network activity for a node by using the concept of degrees -- the number of direct connections a node has. In the kite network above, Diane has the most direct connections in the network, making hers the most active node in the network. She is a 'connector' or 'hub' in this network. Common wisdom in personal networks is "the more connections, the better." This is not always so. What really matters is where those connections lead to -- and how they connect the otherwise unconnected! Here Diane has connections only to others in her immediate cluster -- her clique. She connects only those who are already connected to each other.

Betweenness Centrality: While Diane has many direct ties, Heather has few direct connections -- fewer than the average in the network. Yet, in may ways, she has one of the best locations in the network -- she is between two important constituencies. She plays a 'broker' role in the network. The good news is that she plays a powerful role in the network, the bad news is that she is a single point of failure. Without her, Ike and Jane would be cut off from information and knowledge in Diane's cluster. A node with high betweenness has great influence over what flows -- and does not -- in the network. Heather may control the outcomes in a network. That is why I say, "As in Real Estate, the golden rule of networks is: Location, Location, Location."

Closeness Centrality: Fernando and Garth have fewer connections than Diane, yet the pattern of their direct and indirect ties allow them to access all the nodes in the network more quickly than anyone else. They have the shortest paths to all others -- they are close to everyone else. They are in an excellent position to monitor the information flow in the network -- they have the best visibility into what is happening in the network.

Network Centralization: Individual network centralities provide insight into the individual's location in the network. The relationship between the centralities of all nodes can reveal much about the overall network structure.

A very centralized network is dominated by one or a few very central nodes. If these nodes are removed or damaged, the network quickly fragments into unconnected sub-networks. A highly central node can become a single point of failure. A network centralized around a well-connected hub can fail abruptly if that hub is disabled or removed. Hubs are nodes with high degree and betweeness centrality.

A less centralized network has no single points of failure. It is resilient in the face of many intentional attacks or random failures -- many nodes or links can fail while allowing the remaining nodes to still reach each other over other network paths. Networks of low centralization fail gracefully.

Besides, I take a simple description about the basic concept of prestige.

Degree prestige: A page is prestigious if it receives many in-links. The idea is that actors who are prestigious tend to receive many nominations or choices.

Proximity Prestige: Proximity prestige considers how proximate is to the actors in its influence domain. Define proximity as closeness that focuses on distances to rather than from each actor.

Rank prestige: An important aspect that we have ignored so far in the notions of prestige is the importance of the pages that link to i. Surely, if i receives links from important pages, it is probably important itself.

I am very interested in the ranking algorithm in information retrieval, such as PageRank or Hits. When analyzing social network, we will always deal with the web pages. So there are lots of similar methods or ideas as link analysis in information retrieval.

Link-based techniques for analyzing social networks enhance text-based retrieval and ranking strategies. As we shall see, social network analysis was well established long before the Web, in fact, long before graph theory and algorithms became mainstream computer science. Therefore, later developments in evolution models and properties of random walks, mixing rates, and eigensystems (Motwani & Raghavan, 1995) may make valuable contributions to social network analysis, especially in the context of the Web.

First I want to talk about PageRank, not in detail of the algorithm, just some core ideas. While PageRank and HITS were first presented in the same year (1998), PageRank has emerged as the dominant link analysis model for web search and mining. Like rank prestige, PageRank looks at the number of inlinks, together with the importance of these inlinks. It yields a static ranking, that is computed off-line, for each page, and does not depend on the search queries.

From the perspective of prestige, the following intuitions are used to derive the PageRank algorithm:

• A link from a page pointing to another page is an implicit conveyance of authority to the target page. Hence, the more in-links a page i has, the more prestige it has.
• Pages that link to page i have their own prestige scores. A page with a higher prestige score pointing to i is more important than a page with a lower prestige score pointing to i.
• Since a page may point to many other pages, its prestige score should be shared among all the pages that it points to.

In Google, the crawled graph is first used to pre-compute and store the PageRank of each page. Note that the PageRank is independent of any query or textual content. When a query is submitted, a text index is used to first make a selection of possible response pages. Then an undisclosed ranking scheme that combines PageRank with textual match is used to produce a final ordering of response URLs.  All this makes Google comparable in speed, at query time, to conventional text- based search engines.

PageRank is an important ranking mechanism at the heart of Google, but it is not the only one: keywords, phrase matches, and match proximity are also taken into account, as is anchor text on pages linking to a given page. Search Engine Watch (www.searchenginewatch.com) reports that during some weeks in 1999, Google’s top hit to the query “more evil than Satan” returned www.microsoft.com, probably because of anchor text spamming. This embarrassment was fixed within a few weeks. The next incident occurred around November 2000, when Google’s top response to a rather offensive query was www.georgewbushstore.com. This was traced to www.hugedisk.com, which hosted a page that had the offensive query words as anchor text for a hyperlink to www.georgewbushstore.com.Although the details of Google’s combined ranking strategy are unpublished, such anecdotes suggest that the combined ranking strategy is tuned using many empirical parameters and checked for problems using human effort and regression testing. The strongest criticism of PageRank is that it defines prestige via a single random walk uninfluenced by a specific query. A related criticism is of the artificial decoupling between relevance and quality, and the ad hoc manner in which the two are brought together at query time, for the sake of efficiency.

There is something different of HITs from PageRank. HITS stands for hypertext induced topic search. Unlike PageRank, HITS depends on a query. When the user submits a query, HITS first expands the list of pages returned by the search engine and then produces two rankings of the expanded set of pages: authority ranking and hub ranking.

An authority is a page with many in-links; it may have good content on some topic, and hence it is linked to by many. A hub is a page with many out-links, and serves as a good organizer of the information on a certain topic. The idea behind HITS is that a good hub points to many authorities, and a good authority is pointed to by many good hubs.

How does HITS collect pages to be ranked? Given a search query q, HITS collects a set of pages as follows:

1. Submit the query to a search engine. Collect the t (typically, t = 200) highest ranked pages, which we assume to be highly relevant to q. This set is called the root set W.

2. Expand W by including any page pointed to by a page in W and any page that points to a page in W. The result is a larger set called S. As the set can be very large, the algorithm restricts its size by allowing each page in W to import at most m pages pointing to it into S. The set S is called the base set.

The entire process is generically called topic distillation. User studies (Chakrabarti et al., 1999) have shown that reporting hubs is useful over and above reporting authorities, because they provide useful annotations and starting points for users to start exploring a topic.