Centralities in Network Analysis

摘要

Graphs are one of the most basic representation tools employed in many fields of pure and applied science; they are the natural way to model a wide range of situations and phenomena. The emergence of social networking and social media has given a new strong impetus to the field of "social network analysis"; although the latter can be thought of as a special type of data mining, and can take into account different data related to the network under consideration, a particularly important type of study is what people usually call "link analysis". In a nutshell, link analysis tries to discover properties, hidden relations and typical patterns and trends from the study of the graph structure alone.In other words, more formally, link analysis studies graph invariants: given a family G of graphs under consideration, a V-valued graph invariant [7] is any function ∏ : G → V that is invariant under graph isomorphisms (that is, G ≌ H implies ∏(G) = ∏(H), where ≌ denotes isomorphism).Binary invariants are those for which V = {true,false}: for instance, properties like "the graph is connected", "the graph is planar" and so on are all examples of binary graph invariants. Scalar invariants have values on a field (e.g., V = R): for instance "the number of connected components", "the average length of a shortest path", "the maximum size of a connected component" are all examples of scalar graph invariants. Distribution invariants take as value a distribution: for instance "the degree distribution" or the "shortest-path-length distribution" are all examples of distribution invariants.It is convenient to extend the definition of graph invariants to the case where the output is in fact a function assigning a value to each node. Formally, a V-valued node-level graph invariant is a function n that maps every G ∈ G to an element of V~(N_G) (i.e., to a function from the set of nodes N_(G) to V), such that for every graph isomorphism / : G →H one has ∏(G)(ⅹ) = ∏{H)(f(ⅹ)). informally, ∏ should have the same value on nodes that are exchanged by an isomorphism.Introducing node-level graph invariants is crucial in order to be able to talk about graph centralities [8]. A node-level real-valued graph invariant that aims at estimating node importance is called a centrality (index or measure) [1]; given a centrality index c : N_G →R, we interpret c(ⅹ) ＞ c(y) as a sign of the fact that x is "more important" (more central) than y. Since the notion of being "important" can be declined to have different meanings, in different contexts, a wide range of indices were proposed in the literature.The purpose of my talk is to present the idea of graph centrality in the context of Information Retrieval, and then to give a taxonomic and historically-aware description of the main centrality measures defined in the literature and commonly used in social-network analysis (see, e.g., [3-7]). I will then discuss how centrality measures can be compared with one another, and focus on the axiomatic approach [2], providing examples of how this approach can be used to highlight the features that a certain centrality does (or does not) possess.