Centrality measures for large graphs: exact, approximate, and distributed algorithms

TSAI

Relationships between entities, such as friendships between people and similarities between objects, can be naturally represented as graphs (or networks), where objects are nodes (or vertices) of the graph and edges connect related nodes. Social networks, both online and offline, are a good example of graphs, as are the Web (with web pages that link to each other) and the Internet (as a collection of machines and routers).

Identifying "important" nodes or edges in a graph is a fundamental task in network analysis, with many different applications in fields such as economics, biology, security, and sociology. Over the years, several importance measures, called centrality indices, have been proposed that formalize the concept of importance in different ways.

Measuring centrality

Centrality measures rely on graph properties to quantify importance. For example, "betweenness centrality," one of the most commonly used centrality indices, calculates the fraction of the shortest path through a node, while a node's "closeness centrality" is the average of the sum of the inverses of its distances to other nodes. Even PageRank, Google's original algorithm for ranking web pages, is a centrality measure.

With the proliferation of large networks with millions of nodes and billions of edges, the importance of having scalable algorithms to compute centrality indices becomes increasingly important. Many contributions have been proposed recently, ranging from heuristics that perform very well in practice, to approximate algorithms that provide strong probabilistic guarantees, to scalable algorithms for MapReduce platforms.

TSAI Labs, together with collaborator ISI Foundation, builds centrality measures for large graphs: exact, approximate, and distributed algorithms.