Centrality Algorithms

has a lot of direct connections

is transitively connected to other important nodes

can reach other nodes with few hops

sits on the shortest path of lots of pairs of nodes.

Degree centrality is an important component of any attempt to determine the most important people on a social network. For example, in BrandWatch’s most influential men and women on Twitter 2017 the top 5 people in each category have over 40m followers each.

Two Step graph-based semi-supervised Learning for Online Auction Fraud Detection describes how weighted degree centrality has been used to help separate fraudsters from legitimate users of an online auction. The centrality for fraudsters is significantly higher because they collude with each other to artificially increase prices.

Closeness centrality is used to research organizational networks, where individuals with high closeness centrality are in a favourable position to control and acquire vital information and resources within the organization. One such study is "Mapping Networks of Terrorist Cells" by Valdis E. Krebs.

Closeness centrality can also used in networks where information spreads through all shortest paths simultaneously, such as infection spreading through a social network. Find more details in "Centrality and network flow" by Stephen P. Borgatti.

Closeness centrality has been used to estimate the importance of words in a document, based on a graph-based keyphrase extraction process. This process is described by Florian Boudin in "A Comparison of Centrality Measures for Graph-Based Keyphrase Extraction".

Betweenness centrality is used to measure the network flow in package delivery processes or telecommunications networks. These networks are characterized by traffic that has a known target and takes the shortest path possible. This, and other scenarios, are described in "Centrality and network flow".

Betweenness centrality is used to identify influencers in legitimate, or criminal, organizations. Influencers in organizations are not necessarily in management positions, but instead can be found in brokerage positions of the organizational network. The removal of these influencers could destabilize the organization. More detail can be found in "Brokerage qualifications in ringing operations".

Betweenness centrality can be used to help microbloggers spread their reach on Twitter, with a recommendation engine that targets influencers that they should interact with in future. This approach is described in "Making Recommendations in a Microblog to Improve the Impact of a Focal User".

Personalized PageRank is used by Twitter to present users with recommendations of other accounts that they may wish to follow. The algorithm is run over a graph which contains shared interests and common connections. Their approach is described in more detail in "WTF: The Who to Follow Service at Twitter".

PageRank has been used to rank public spaces or streets, predicting traffic flow and human movement in these areas. The algorithm is run over a graph which contains intersections connected by roads, where the PageRank score reflects the tendency of people to park, or end their journey, on each street. This is described in more detail in "Self-organized Natural Roads for Predicting Traffic Flow: A Sensitivity Study".

PageRank can be used in an anomaly or fraud detection system in the healthcare and insurance industries. It helps find doctors or providers that are behaving in an unusual manner, and the score can be fed into a machine learning algorithm.