Arianna Sacco : « Between you and me – Betweenness centrality and related measures »

by dave

« One of the most common measures used in network analysis is betweenness centrality. In this article, you will learn how to make use of it and which algorithms are used to calculate it.

In the previous article in this series on network analysis in archaeology, I discussed the first one of the main four measures, or mathematical algorithms, used in network analysis: the degree centrality. I have also discussed further algorithms derived from the degree centrality.

In this article, I will discuss the second one of the measures: the betweenness centrality. This measure shows how important the examined entity is as intermediary, a bridge, between other pairs (or even groups) of entities in the network, or an in-between between third parties (if you prefer).

In other words, betweenness centrality detects entities that have the highest capacity of linking other entities in the chains of contacts in a network and that, as a consequence, can have control over the flow and circulation of objects/resources/information/ideas.

The betweenness centrality

In technical terms, the betweenness centrality of an entity measures how often the examined entity is on a geodesic between other entities. A geodesic is the shortest path, or sequence of links, between two entities in a network.

For example, in Figure 1, Edfu and Mostagedda are not directly linked, because they have no types of Tell el-Yahudiyah ware in common, but they are connected through Tell el-Dab’a and Tell el-Yahudiyah, and the latter are also connected between them, because they have types in common.

Therefore, to go from Edfu to Mostagedda (but also vice-versa) the following routes are available:

  • Edfu – Tell el-Dab’a – Tell el-Yahudiyah – Mostagedda
  • Edfu – Tell el-Dab’a –Mostagedda
  • Edfu – Tell el-Yahudiyah – Mostagedda

As you can see, the last two options have fewer steps, therefore they are the geodesics between Edfu and Mostagedda – and yes, you can have more geodesics, and the denser the graph, the more geodesics will be present.

Geodesics

Mathematically, betweenness centrality is based on the proportion of all the geodesics – i.e. shortest paths – between two nodes that the geodesics that include the examined entity; this can be referred to as partial betweenness. The partial betweenness can be calculated with the following formula:

bijm=gijmgjm

Here, gijm represents the number of geodesics between j and m containing j (the entity examined), while gjm represents the number of geodesics connecting j to m. From this, is possible to calculate the betweenness centrality:

CB(i)=∑jn∑mnbijm(i≠j,i≠m)

This is summing the results given by calculating the partial betweenness of the examined entity, i, for each pair of nodes, represented by j and m.

Going back to Figure 1, if you want to know the betweenness centrality of Tell el-Dab’a, first you take each pair of the other sites (e.g. Harageh and Abydos, Rifeh and Sedment, Hu and Abydos, and so on), and you calculate the ratio between the geodesic that pass by Tell el-Dab’a and the geodesics that do not. Then, you sum up the calculated ratios.

In a weighted network, such as the one in Figure 1, both undirected and directed, this measure is also based on the weight of the links, following the assumption that more similarities forming a link mean more contacts and, thus, a lower cost to maintain them. You can also calculate the measures for edges, but I will write about that in a future article.

Central points

In a graph, the most central point is the one in the middle of a star. Mathematically, the centrality of this point corresponds to the following formula, referred to as maximum betweenness centrality:

maxCB=n2−3n+22

Where n represents the number of nodes in a graph. Therefore, this formula can calculate the highest betweenness centrality possible in a network, namely value of the most central point in a graph.

From this, you can calculate relative betweenness centrality of an entity, by dividing the double of its betweenness centrality by the maximum betweenness centrality in the same network.

The formula is as follows:

CB(i)′=2CB(i)n2−3n+2

This is the ratio between the betweenness centrality of an entity and the numerator of the maximum betweenness; you need to double the betweenness centrality because the maximum betweenness is not halved (therefore is double than in the previous formula).

At this point, it can seem apparent that the betweenness centrality, while examining the role of each single entity in the network, takes into account the entire structure of the network and it is based on its position in the network.

Network measures

in the previous article, I mentioned that there are centrality measures, concerning the single entities, and network measures, concerning the structure of the entire network.

A network measure that can be calculated from the betweenness centrality is the betweenness centralization, which is given by dividing the sum of the variations of the betweenness centrality scores of all the entities of a network, by the maximum variation in betweenness centrality scores in the same network.

It is given by the formula:

CB()=∑in(CB(∗)′–CB(i)′)Max(∑in(CB(∗)′−CB(i)′)

CB(∗)′ is the betweenness centrality of the network’s most central vertex, and CB(i)′ is the betweenness centrality of any other entity in the network. Basically, you take the point with the highest betweenness, calculate the difference between this and the betweenness centrality of each other entity in the network, you sum all the differences, and you divide this by the maximum difference detected. This is useful if you want to control the entire graph and get a general idea of its structure.

Applying network measures

What does this measure mean, when applied to archaeological material? In the case of my research, the betweenness centrality was determined by how often a site was the find place of (types of) objects that create connections between other sites. Therefore, this measure would put focus for instance on a site which features objects of multiple types that are found separately at other sites, or on a site which features a particular common type, namely a type widely found at the sites.

Because of the fact that my data did not allow me to take directions into account, I could not say where the objects were coming from and where they were going. However, places with a high betweenness centrality funnelled the connections in the network and bring the material culture of other sites together. Therefore, one possibility is that such places could be interpreted as places of exchange or (re)distribution centres for these objects.

A few words about something that surprised me when I started my project: it is common to have a big difference between the entities you examine, when it comes to network analysis, as you can see in Figure 1. Therefore, be prepared to see that in your analysis a few entities have a high betweenness centrality, while most of the others have a very low one.

Because of its nature, betweenness centrality detects what in my opinion can be compared to neuralgic centre(s) of the network, points that are vital in maintaining the connections by ensuring that the flow continues from one point to the other. Of course how many vital points there are depends on the kind of network, but more often they will not be many.

The main problem is that betweenness centrality considers only geodesic paths, in other words it assumes that whatever flows through the network travels only along the shortest possible paths, in the most efficient way. However, reality is more nuanced and paths, and geodesic paths, are only one of the possible ways that something can move in a network. I will talk more about this in a future article, after discussing all the main measures.

For now, suffice to say that there are multiple ways in which anything can circulate in a group, counting if it spreads only form one or multiple entities, if goes to one or more entities at the same time, and if it passes one or multiple times through the entities and the connections of the network.

Moreover, it appears that betweenness centrality is more prone to Type I errors (“false positives”), therefore leading to overestimations. Nevertheless, it has been shown to be useful to understand network changes and, when examining the flow in a network, the frequency of passage, and to be less sensitive to Type II errors (“false negatives”, which lead to under-estimation).

The density of a network

One measure that can in some cases influence the betweenness centrality is the density of a network. This is the proportion between the links that are actually present in the network and the maximum number of links that the same network could possess.

When the density is at its maximum, the network is called complete: each node is connected to all the other nodes of the network. This measure reveals the general connectedness of a network, but it depends on the size of the network, so that it is less useful when comparing networks of different sizes.

It is given by the following formula:

d(G)u=mn(n−1)2=m×2n(n−1)=2mn(n−1)

Here, m is the number of edges and n is the number of nodes in a network.

Closing remarks

Despite being heavy on the mathematics, I hope this article gives you an idea of how you can use the measures discusses. Should you be using it? As always, it depends on your data, your questions, and the kind of network you are analysing.

Betweenness centrality gives the idea of a flow passing through specific points where a specific route on a number of times. If your data allow for an approximation of this model, then you can consider using it. You should always bear in mind that studying networks is making an ideal model to explain real-life phenomena.

Therefore, if what you are studying can be idealized as a network, with flow and circulation of ideas/knowledge/information/objects/resources, then it is most useful. Moreover, each measure has some assumptions about how the flow happens, as I mentioned earlier about geodesic paths. If this assumption is applicable to what you are studying, then also the measure will be informative for you.

Further reading

Suggestions for further reading are listed below:

  • J.M. Bolland, “Sorting out centrality. An analysis of the performance of four centrality models in real and simulated networks”, Social Networks 10 (1988), pp. 233-253.
  • S.P. Borgatti, “Centrality and network flow”, Social Networks 27 (2005), pp. 55-71.
  • L.C. Freeman, “A Set of Measures of Centrality Based on Betweenness”, Sociometry 40 (1) (1977), pp. 35-41.
  • L.C. Freeman, “Centrality in social networks. Conceptual clarification”, Social Networks 1 (1979), pp. 215-239.
  • L.C. Freeman, S.P. Borgatti, and D.R. White, “Centrality in valued graphs: A measure of betweenness based on network flow”, Social Networks 13 (1991), pp. 141-154.
  • J. Scott, Social Network Analysis (fourth edition, 2017).
  • D.R. White and S.P. Borgatti, “Betweenness centrality measures for directed graphs”, Social Networks 16 (1994), pp. 335-346.

Tagged with Data scienceEgyptiansMethodNetwork analysis »

Between you and me : Betweenness centrality and related measures, by Arianna Sacco

by dave
by dave

Lectures / Partage(s) / Curiosité(s) / Invitation(s) au voyage :

  • Canadian Innovation Week (du 17 au 21 mai 2021) : « From Problems to Possibilities« 
  • Technology transfer: Career-boosting computing skills for girls in Argentina – by Nikki Forrester
  • [via publication/partage de la page facebook] The Peasant Press Forum (19 juillet 2021)
    • [« Too often, the struggles of peasant farmers around the world are kept in the dark. Without visibility, the exploitation they face at the hands of corporations and governments continues unchallenged. It’s time for that to change. Peasant groups from around the world are standing up and demanding that their stories be heard. It’s time to listen. »]
    • [« The Peasant Press Forum is an opportunity for international media organizations and peasant organizations to connect and bring those stories to light. This digital event will feature groups from Asia, Africa and Latin America who are on the frontlines of the global food sovereignty movement. Media and peasant groups must register prior to the event to be able to attend. »]
    • [« Peasant communities fighting for their rights to land and justice face ever-growing threats to their livelihoods and lives. Their safety is vital. We ask for media representatives to honor the needs of the participants. »]
  • (via publication/invitation/partage de la page facebook du Rutgers Advanced Institute for Critical Carribean Studies reprenant celle de la page du Corredor Afro) :
    • « Spirit Women on a conversation around the Ashé of connected womanhood, shared ancestral wisdom, and the creation of a knowledge-based afro network for the future. »
    • « In honoring our womanhood, we acknowledge our ancestral mothers and their continued spiritual presence within our lives. We recognize the powers of spiritual healing, divine knowledge, artistic creativity, ability to earn and sustain our lives and that of family and community – ASE. »
    • « May 12, 2021 »
    • « Creative Justice Initiative Corporación Piñones se Integra – COPI Marta Moreno Vega Mayra Santos Febres Shantrelle Patrice Lewis »
  • Transforming Anthropology
  • Community Voices from Four Continents – InsightShare
  • Han Suyin: The little voice of decolonizing Asia – by Feng Cui & Alex Tickell
  • [Pétition via publication/invitation/partage de la page facebook People’s Coalition on Food Sovereignty – Global] : Stop the corporate hijack of the 2021 UN Food Systems Summit!
    • [extrait : « The UN Food Systems Summit is fast approaching but it’s shaping to be an event driven by corporate agenda of profitability — a far cry from the « People’s Summit » it aims to be. It’s time to take back the wheel and put people’s right over profit in reforming our food systems. »]
  • [Pétition via publication/invitation de la page facebook du Center for Environmental Concerns – Philippines] : Filipino fishers urge UN to act on Chinese incursions in West PH Sea
    • [«  »“Our petitions complement the very principles of the arbitral ruling against China. These include the immediate pullout of Chinese personnel in our territorial waters, respect the rights of our fishers, and demilitarize our traditional fishing grounds,” PAMALAKAYA national chairperson Fernando Hicap said in a statement. » – « “Our appeal is in the framework of upholding the basic rights to food and livelihood of our fisherfolk, who are the direct victims, and for the peaceful, diplomatic and non-military resolution to the Chinese aggression and plunder. » » – « The group said it filed the petitions due to « lack of concrete and decisive actions » from the Duterte administration. » – « “The Filipino fishers are tired of Mr. Duterte compromising our sovereignty in the name of foreign loans and now, vaccines,” Hicap said. » »]
  • The Social Life of Standards : Ethnographic Methods for Local Engagement – edited by Janice E. Graham, Christina Holmes, Fiona McDonald, & Regna Darnell
    • [« Through twelve ethnographic case studies, The Social Life of Standards reveals how standards – political and technical tools for organizing society – are developed, applied, subverted, contested, and reassembled by local communities interacting with norms often created by others. Contributors explore standards at work across different countries and contexts, such as Ebola biomedical safety precautions in Senegal, Colombian farmers contesting politicized seed regulations, and the application of Indigenous standards to Canadian environmental assessments. They emphasize the uncomfortable fit between the often messy and inconsistent implementation of standards in the real world and the monolithic, non-negotiable criteria presupposed by external forces. Overt conflict arises when standards misrepresent important local (or global) realities. How do communities actively challenge and re-create standards that do not meet their needs? »]
    • [« The Social Life of Standards provides an important anthropological perspective on the articulation of standards. The goal is to arrive at a more reflexive process that offers progressive engagement at the local level. Ultimately, we need an effective balance between evidence-based science, the social contexts that inform more useful and appropriate standards, and the inherent potential for activism. »]
    • [« This book will be invaluable for scholars and students in anthropology, political and environmental studies, and science and technology studies; for ethnographers and researchers who conduct participatory research; and for regulators, policy makers, and the citizen reader. »]
  • Here’s why Indigenous economics is the key to saving nature – by Krystyna Swiderska
  • Practical guide helps negotiators put equity at the heart of the new global biodiversity framework – by Ebony Holland & Dilys Roe
    • [extrait : « Conservation efforts, while critical to reducing biodiversity loss, often fail to treat people fairly. This undermines the sustainability of these efforts and can further marginalise already vulnerable people. A new guide offers negotiators practical steps for embedding equity in the new global biodiversity framework. » – « Negotiators are under pressure to work together to finalise a framework that truly delivers on its mission: to live in harmony with nature by 2050. » – « Calls for stronger focus on equity : The GBF failing to recognise equity was one of the thorny issues emerging from recent informal subsidiary body meetings. Various country statements and major stakeholder groups highlighted that equity must be central to efforts to reverse biodiversity loss. » – « Conservation efforts, such as restricting access to protected areas, can come at the expense of Indigenous Peoples and local communities through a loss of land, livelihoods and identity. These groups offer substantial knowledge, skills and experience to support conservation goals that are often overlooked. » – « Yet the current draft GBF falls short on emphasising the importance of equity for effective conservation efforts; a concern that will be raised again by parties during formal negotiations this month and next, and at the major mid-year negotiations in August. » – « Unless calls are met for the GBF to recognise the importance of equity in conservation, there remain doubts over whether it can truly deliver outcomes for both people and nature in the long term. Equity featured in the Aichi Targets and must be central to the GBF also. » – « Equity should also be central to the negotiation process » – « Building synergies for equitable outcomes »]
    • Strengthening equity in the post-2020 Global Biodiversity Framework (A Guide for Negotiators) – by Johannah Bernstein, Valerie Heinz, Renske Schouwink, Marc Meunier, Ebony Holland & Dilys Roe / [Bernstein, J., Heinz, V., Schouwink, R., Meunier, M., Holland, E., Roe, D. (2021). Strengthening equity in the post-2020 Global Biodiversity Framework. IIED, London.]
  • Le mont Ararat, butin de guerre de la Turquie – par MARIE POULAIN & JEAN MICZKA
    • [« Après plusieurs années de restrictions, le plus haut sommet de Turquie est à nouveau accessible depuis février 2021. Ankara désire en faire un haut lieu touristique sans perdre de vue la révolte kurde qui depuis un siècle rythme la vie du mont Ararat, resté pour les Arméniens le berceau de leur nation. »]
  • The Workers Who Sued Uber and Won, by Wilfred Chan
    • [extrait : « The UK Supreme Court has ruled in favor of Uber drivers, declaring them workers and not independent contractors. But to beat the platform capitalists, it is urgent that we start to treat digital rights as worker rights. »]
  • A healthier pace – by Josho Brouwers & Matthew Lloyd
    • The Odyssey : A peacetime epic, or a critique of the values of the Heroic Age? – by Rosie Roberts
      • [« Compared to Homer’s Iliad, the Odyssey appears to be set in a world at peace. But despite the epic taking place far from the Trojan battlefield, violence still plays an important role. »]
  • The long shadow of conflict: Unexpected links between war, interpersonal violence and social cohesion – by Jocelyn Kelly
    • [« How does violent conflict affect the way people perceive their communities, how treat each other and how they think of themselves, even years after hostilities end? The session will first present findings on the long-term, hidden ways that political conflict can destabilize communities through a “contagion” of political violence into gender-based violence (GBV). »]
    • [« The session will go on to explore some surprising links between conflict, GBV and deeply impactful yet hard-to-measure phenomena such as personal resilience, self-efficacy, “othering,” envy and social cohesion. A recent population-based impact evaluation from eastern DRC provides insight into how these phenomena relate to both perpetration and victimization of GBV. The data also point to some of the pathways that might help or hinder violence to persist and morph as countries seek to move from conflict to post-conflict recovery. »]
  • Marginalised Histories of the Second World War
    • [« As well as the impetus behind the special issue and its contents, the round table will address the questions it raises about commemoration and how the war has been remembered as well as how to research and write histories that have been marginalised. »]
  • What is Assyriology?, by Nicholas Postgate
by dave
by dave

by dave
by dave
by dave
by dave
by dave
« Pope Francis will not apologize for the Catholic Church’s role in Canada’s residential schools and the trauma experienced by their students. A papal apology was one of the 94 recommendations made by the Truth and Reconciliation Commission. »
by dave
by dave
by dave

Les commentaires sont fermés.

Ce site vous est proposé par WordPress.com.