A comparative evaluation of social network analysis tools: performance and community engagement perspectives

Comprehending the fundamental community structure is crucial for revealing concealed patterns, recognizing pivotal nodes, and acknowledging the network’s utility in the network’s vast and interconnected realm. Community detection algorithms play a crucial role in this endeavour as they aim to partition networks into significant groups or communities based on node relationships. Louvain algorithm introduced by Blondel et al. (2008) is one of the essential methods for detecting communities in large networks. The Louvain method is a sophisticated optimization algorithm that iteratively maximizes the modularity of network partitions using a multi-level approach. The quality of each partition is measured using modularity by comparing the total edges in a community to the anticipated size in a random network. Based on Newman (2010) modularity can be expressed using Eq. 1.where m is the number of edges or sum of edges, A is the adjacency matrix of graph G, \(k_i\) is the degree of I, \(\gamma\) is the resolution parameter, and \(\delta (c_i c_j)\) is one if i and j are in the same community and 0 in all other cases.

The modularity algorithm and multi-level community detection algorithm (Blondel et al. 2008) are implemented in EasyGraph, NetworkX, and Igraph. Since the modularity functions require a partition as an input, the multilevel community partition is used as an input to the modularity function for each graph and network tool. Graph-tool implements Newman’s modularity (Newman 2006) and not the multilevel community detection and, as such, was not tested in this research since the community partition is required as an input.

The average clustering coefficient of a graph G is calculated as the mean of the local clustering coefficients of all nodes in the graph (Watts and Strogatz 1998). This metric indicates the graph’s nodes’ general propensity to group into communities or clusters. The average clustering coefficient is given by Eq. 2 (Newman 2003) where n is the number of nodes in the graph, and \(C_i\) is the local clustering coefficient for node i. A critical feature of many complex networks in the real world is their tendency to form tightly knit clusters, which may be inferred from the average clustering coefficient. Saramäki et al. (2007) presented a generalization to weighted networks. These generalizations provide a more sophisticated comprehension of clustering patterns in weighted networks, where link strength is important. Understanding the structure and operation of complex networks requires understanding their connectedness and how nodes are grouped based on the weights of the edges connecting them. Similarly, Barrat et al. (2004) introduced a different approach for calculating the average coefficient in a weighted graph implemented in Igraph. The average clustering coefficient is implemented for the undirected and directed graphs in NetworkX, EasyGraph, Graph-tool and Igraph.

A strongly connected component in a directed graph refers to a group of vertices where each vertex can be reached from every other vertex within the group (Tarjan 1972). Tarjan (1972) proposed a highly efficient approach for identifying strongly connected components (SCCs) in a directed graph. Tarjan’s technique utilizes depth-first search (DFS) and a stack-based methodology. The technique conducts a depth-first search (DFS) network traversal and keeps track of a stack of nodes that have been visited but have no strongly connected component (SCC). Nuutila and Soisalon-Soinen suggested a tweak to Tarjan’s algorithm to enhance efficiency, as documented in their publication (Nuutila and Soisalon-Soininen 1994). Nuutila and Soisalon-Soinen’s technique aims to find strongly connected components (SCCs) more straightforwardly without relying on the stack-based mechanism employed by Tarjan’s algorithm. The approach proposed by Nuutila and Soisalon-Soinen also employs a depth-first search (DFS) traversal of the network, but it circumvents the need for a stack to keep track of vertices. NetworkX uses the Tarjan algorithm with Nuutila modifications. All the tools considered in this research implement the SCC module for directed graphs only, except Igraph, which accepts both directed and undirected graphs.

A biconnected component is a maximal subgraph in which at least two disjoint paths connect any two vertices. This means that if any single vertex is removed from a connected component, the component remains connected. Details about the method implemented in each tool need to be clarified, but NetworkX provides a reference to Tarjan (1972) for their algorithm optimization. The connected components module is implemented in all the tools explored in this research.

The density of a graph is a measure of how many edges it has compared to the maximum possible number of edges it could have. The density for an undirected and directed graph are given in Eqs. 3 and 4 respectively (Hagberg et al. 2008)where m is the number of edges and n is the number of nodes. The density module is available in the NetworkX, EasyGraph, and Igraph libraries. Equation 4 represents the implementation of the density module in NetworkX. The implementation details of the density module are unclear from the Igraph and EasyGraph documentation.

Eigenvector centrality measures the influence of a node in a network (Zaki and Meira 2014). All nodes in the network are given relative scores based on the idea that a node’s score is influenced more by connections to high-scoring nodes than by the same connections to low-scoring nodes. When a node has a high eigenvector score, it indicates that it is linked to numerous other nodes that also have high scores (Newman 2008; Negre et al. 2018). Eigenvector centrality was first defined generally in networks based on social connections by Berge (1960) and was subsequently popularised by Bonacich (1972) as an essential measure in link analysis.

Generally, the eigenvector centrality x is given as the solution ofFormally, it can be written aswhere A is the adjacency matrix and \(\lambda\) is the largest eigenvalue. NetworkX, Igraph, and Rustworkx implement the eigenvector centrality module. The implementation in NetworkX is shown in the equation above. NetworkX implemented an additional module that uses SciPy sparse eigenvalue solver to find the eigenvector; however, only the native implementation was examined in this study. The eigenvector centrality module is implemented in Rustworkx based on Treinish et al. (2022).

The betweenness centrality of a vertex v in a graph measures the extent to which the vertex lies on paths between other pairs of vertices (Watts and Strogatz 1998). Specifically, it is defined as the number of shortest paths between all pairs of vertices s and t that pass through v, divided by the total number of shortest paths between s and t in the graph (Freeman 1977). Formally, the betweenness centrality CB(v) of a node v is given by Eq. 6 (Brandes 2001).The betweenness centrality module is available in NetworkX, Rustworkx, EasyGraph, Graph-tool, and Igraph. The module is implemented in Rustworkx based on the method described in Brandes (2001) and by Eq. 6. It is not clear how the module is implemented in the other tools. However, in NetworkX, a normalization procedure based on Borgatti and Halgin (2011) is implemented for stability.

A minimum spanning tree (MST) of a connected, undirected graph is a subgraph that is a tree (a connected acyclic graph) and that includes all the vertices of the original graph with the minimum possible total edge weight (Hagberg et al. 2008). In other words, an MST is a subset of the edges of the original graph that connects all the vertices with the minimum total edge weight. There are several algorithms for finding the MST of a graph, including Kruskal’s algorithm (Kruskal 1956) and Prim’s algorithm (Prim 1957). The main difference between the two algorithms lies in their approaches to selecting edges to include in the MST. Kruskal’s algorithm is greedy and builds the MST by repeatedly adding the shortest edge, which does not create a cycle in the MST. It starts with a forest of singleton trees (each node is its own tree) and repeatedly selects the shortest edge connecting two trees until all nodes are in a single tree. Kruskal’s algorithm sorts all the edges in the non-decreasing order of their weights and then processes them individually, adding an edge to the MST if it does not create a cycle. Prim’s algorithm is also a greedy algorithm that builds the MST by starting from an arbitrary node and repeatedly adding the shortest edge that connects a node in the MST to a node outside the MST. It starts with a single vertex and grows the MST by adding the shortest edge that connects a vertex in the MST to a vertex outside the MST until all vertices are in it. Prim’s algorithm maintains a priority queue of vertices outside the MST, where the priority of a vertex is the weight of the shortest edge connecting it to the MST.

Kruskal’s algorithm (Kruskal 1956) is implemented in Rustworkx and NetworkX. The choice of algorithm in Graph-tool depends on the user’s provision of the root node. Prim’s algorithm is used if the root is provided, while Kruskal’s is used if not. Prim’s algorithm is implemented in Igraph. In addition to Prim’s and Kruskal’s algorithms, NetworkX implements a third algorithm called the Boruvka algorithm (Nešetřil et al. 2001).

The average path length is a measure used in network analysis to determine the typical distance between nodes in a graph. It represents the average number of steps along the shortest paths for all possible pairs of network nodes. This metric provides insights into how efficiently information or influence can travel across the network (Newman 2010). Mathematically, if d(i, j) represents the shortest path distance between node i and j and n is the total number of nodes in the network, then the average shortest path length A is given by Eq. 7The average shortest path length is available in NetworkX, Igraph, and EasyGraph. The method was tested for all datasets but failed for the ego-google dataset with NetworkX and EasyGraph (giving “error: Graph is not strongly connected").

Social network analysis (SNA) plays a crucial role in understanding the structures, relationships, and behaviors that emerge within complex networks. To conduct such analysis effectively, modularity, clustering, centrality, and connectedness can be helpful in analyzing, interpreting, and predicting social phenomena.

For instance, identifying tightly knit groups using modularity allows researchers to reveal hidden interaction clusters when analysing social networks, such as online communities or professional relationships. These clusters can help uncover subcultures, interest groups, or collaborative teams, shedding light on how information flows within specific segments and how influence may be concentrated (Newman 2010; Akinnubi et al. 2024). Centrality measures like eigenvector and betweenness centrality are critical when identifying key players in a network. In organizational analysis, eigenvector centrality helps pinpoint individuals whose connections to other influential members, such as decision-makers or opinion leaders, amplify their importance (Howlader and Sudeep 2016). Betweenness centrality becomes invaluable in communication networks, where bridging nodes are often critical for controlling or disrupting information flow. For example, understanding the role of a single node in connecting disparate parts of a network can be instrumental in crisis communication or network defense (Kuzubaş et al. 2014).

In transportation or logistics networks, concepts like the minimum spanning tree and shortest path calculations are essential for optimization tasks (Shahin and Jaferi 2015). A transportation planner developing a cost-efficient route network may employ the minimum spanning tree to save construction expenses while maintaining connection. Also, the average shortest path length quantifies network efficiency-shorter paths signify enhanced accessibility, which is essential for urban planning and emergency response systems.

Biological and epidemiological networks benefit immensely from measures of clustering and connectivity. In the study of disease transmission, clustering coefficients highlight localized outbreaks and potential superspreader events (Molina and Stone 2012). Meanwhile, strongly connected components help epidemiologists model the robustness of a network’s transmission pathways, allowing them to identify the minimum interventions needed to break cycles of infection (Pastor-Satorras et al. 2015). Network density helps understand the intimacy of interactions in friendship networks or gauge connectivity in organizational structures, and density helps frame broader questions about the network’s purpose and function. For example, a sparse network might indicate inefficiencies or gaps in communication, while a highly dense network might suggest redundancy or resilience.