A Modular Framework for
Centrality and Clustering in Complex Networks

Complex networks [9] are a form of structured data that model interactions among individuals in diverse real-life applications. New instances of complex networks may be studied with existing techniques, or may motivate the introduction of new approaches. An example of a relatively recent and fast evolving complex network is the Bitcoin network, where individuals or nodes are Bitcoin addresses, and edges represent transactions from one address to another; they are thus directed and weighted. There are many reasons to study the Bitcoin network and other cryptocurrency networks as complex networks: understanding their topology and their evolution over time in turn offers economic or societal insights. Centrality analysis and clustering (also known as community detection) are two popular techniques that are used to study network structures and could be applied.

Centrality: The identification of key individuals in a complex network is often done using centrality, a family of measures that captures the importance of nodes in a graph. Centrality measures are often categorized (see Figure 1) by either flow or walk structure. (i) Flow-based measures come with a 2-dimensional typology [6]: the trajectory of the flow (categorized as - geodesics, paths where neither nodes nor edges are repeated, trails where nodes are repeated but edges are not, and walks, where both nodes and edges can be repeated) and the method of spread (which includes - transfer of an atomic flow, duplication or replication of the flow or a split of a volume conserved flow). (ii) Walk structure-based measures are partitioned into radial centralities (counting walks which start/end from a given vertex, e.g. the degree and the eigenvalue centralities) and medial centralities (counting walks which pass through a given vertex, e.g. betweenness centrality).

Our focus is on flow-based measures, motivated by the study of phenomena such as the movement of cryptocurrencies across a network from one sender to a receiver, where the volume of the flow is conserved. In [36], it was argued that the existing flow-based centrality measures back then left a void in the typology because they did not capture well the idea of path-transfer flow. Accordingly entropy, as a measure of uncertainty of dispersal, was advanced as a new centrality measure. The idea was modified in [23], where the path restriction was relaxed from the original idea of [36], allowing for the study of the flow as a random walker using a Markov model.

In order to distinguish senders from receivers, and consider equivalent or distinct (as the need of a specific analysis might be) the users involved in transactions involving large amounts from users carrying out large number of transactions of small amounts, and other such nuances, it is desirable to have the flexibility to consider the directionality and weights of the edges, which could carry their own semantics. While a notion of weighted degree centrality has been proposed [28], this paper proposes a notion of flow-based centrality which is seamlessly adjustable to undirected, directed and/or weighted graphs. Akin to [23], our work uses a random walker starting its walk at any given node, whose centrality is captured by the spread of the walk, measured in terms of entropy, and an absorption probability is used to model the walker stopping at any destination. While [23] rendered the usage of entropic centrality more practical than [36] by introducing the idea of a random walker, it also has limitations both in the theoretical exploration of the concepts as well as the resulting practical implications. These limitations, together with the potential of the ideas themselves, serve as motivations for our current work. Particularly, we provide, among other improvements, closed form expressions to characterize the behaviour of the walker. The specific details are elaborated when we discuss our contributions below.

Graph clustering: A set of nodes that share common or similar features are considered to comprise a cluster in a network. A general understanding of a good cluster is that it is dense (nodes within are well connected), and have few connections with the rest of the network [35, 22]. Beyond that, there is no unique criterion that necessarily captures or reflects the quality of the clusters. Depending on the particular aspects being captured, different approaches may be relevant, and likewise, different outcomes may be expected and desirable. In [35], two broad families of graph clustering methods have been identified (see Figure 1) - (i) those based on vertex similarity in some manner, e.g., distance or similarity measure which may or not take into account structural information (for instance, web-page similarity may consider only content similarity, or may also consider the hyperlinks to determine similarity), adjacency or connectivity based measures; and (ii) those based on cluster fitness measures, including density and cut-based measures, e.g., modularity. In [22], the former are referred to as pattern based, since these methods go beyond basic edge density characteristics. They include algorithms relying on random walkers [1, 4, 16], where the basic premise is that random walks originating at a given ‘query’ node is more likely to stay confined within a subgraph which forms a local community containing the query node, than to visit nodes outside said community. The probability distribution of a random walker’s visit (and absorption) at different nodes in the graph is used as a signal to identify cluster boundaries.

It is observed in [22] that while numerous clustering algorithms exist for undirected (weighted) graphs (see [35] for a survey of well known clustering techniques for undirected graphs), clustering algorithms for directed graphs are fewer. Most algorithms rely on creating an “undirected” representation of the directed graph considered, which may result in the loss of semantics and information contained in the directionalities. Examples of notable exceptions where the clustering algorithm is designed specifically for directed graphs are the information flow approaches of [34], where clusters are identified as subgraphs where the information flow within is larger compared to outside node groups, and [16], where an information flow-based cluster is a group of nodes where a random walker (referred as surfer in the work) is more likely to get trapped, rather than moving outside the group. Tellingly, the other random walker based approaches mentioned above, namely [1, 4], because of the additional constraints imposed on the walkers in those algorithms, are only suitable for undirected unweighted graphs.

Since directionality is of importance in many set-ups such as the example of a cryptocurrency network, we will focus on clustering algorithms that can handle both (un)directed and/or (un)weighted graphs, and thus we explore flow circulation based algorithms, which falls within the pattern based (vertex similarity) family of graph clustering algorithms. This choice has a natural coupling with our proposed entropic centrality measure. Under the premise of confinement of flows within a subset of nodes as a way to interpret community structures, one may further consider the flow using any of the many characterization of flows described above in the context of centrality measures, including those supporting the treatment of directed and weighted graphs, each in turn capturing distinct real world phenomena. We would like to emphasize that these distinct approaches of interpreting the flows are not meant to compete with each other (let alone, compete with other clustering algorithms such as those based on local density), and are instead targeted at modelling and capturing distinct behaviors. Given a complex network which is inherently both directed and weighted, e.g., the Bitcoin network, one may need to study its properties considering its directionality, with or without the influence of weights, considering possibly different interpretation of weights, or just its bare topology. It is thus important to have a single clustering method with enough versatility to accommodate and instantiate the spectrum of combinations. Our proposed approach is designed to meet this particular objective.

Organization. The paper is logically organized in two halves: the first part (Sections 2 and 3) is dedicated to the centrality analysis, while the second (Section 4), which relies on the first part, delves into the clustering algorithm. Relevant experiments are reported within the corresponding sections.

In Section 2, we carry out a study of the proposed Markov entropic centrality for unweighted (un)directed graphs. We coin the term ‘Markov’ entropic centrality, as opposed to the original path based model studied in [36], because our model leverages the random walks being absorbed in an abstraction called auxiliary nodes with certain probability, and the future steps of the random walker depends solely on its current location, irrespective of its past. We analyze the behavior of this centrality as a function of (a) the probability that the walker stops at given nodes, and (b) time (or number of steps in the walk). Results are analytically proven in terms of bounds and a closed form expression captures the asymptotic behavior of the random walk probability distribution for unweighted directed graphs (undirected graphs can be readily captured by introducing directed edges for both directions), in contrast to the numerical computations carried out in [23]. An immediate practical implication of such a closed form solution instead of reliance on numerical computations is computational efficiency and scalability of the model. Our analysis provides a thorough understanding of the role of an associated parameter termed as the absorption probability, as well as the flexibility to explore the probability being a constant at all nodes, or being dependent on the individual nodes’ degrees — which in turn makes the model versatile to capture different situations, and enables to reason about the choice of the parameter. This is in contrast to the ad-hoc choices used for experiments in [23]. Finally, we introduce the notion of Markov entropic centralization which we study analytically in the asymptotic time regime as a way to provide further insights regarding the relative importance of the nodes.

In Section 3, we generalize the theory of entropic centrality for weighted graphs, taking into account the need to accommodate different interpretations of edge weights, and its competition with number of edges, in determining node centrality, e.g., tune the model as per the need of an analysis to let an edge with weight 3 have either more or less or equal contribution to a node’s centrality as three edges of weight 1. We refer to [28] for a more elaborate discussion on interpreting centrality for weighted graphs. This is furthermore in contrast to the treatment in [23], where weighted graphs are dealt with by changing the transition probabilities of the random walker as per edge weights, which is one specific instance within our tunable model.

Overall, Sections 2 and 3 result in our first set of contributions, which is vis-à-vis entropic centrality. We provide (i) a generalization of the entropic centrality model, which can be tuned to capture a spectrum of combinations in terms of the role of the edges’ weights and directionality, accompanied with (ii) a mathematically rigorous analysis which helps understand the role of the model parameters and choose them judiciously, and ultimately resulting in (iii) a computationally, significantly efficient and thus scalable model with respect to prior work.

Section 4 contains the proposed clustering algorithm. The above analysis of the random walker probability distributions carried out in the context of entropic centrality, accompanied with an analytical study of the graph centralization measure which captures how tightly the graph is organized around high centrality nodes, directly lends itself to the design of a novel graph clustering (community detection) algorithm, which amortizes the computations carried out for computing the node centralities. Foremost, from the study of the (absorption) probability distributions of the random walkers and the resulting entropic centrality scores of the nodes, we observed that: (i) nodes with a low entropic centrality have local clusters where ties are relatively strong, while nodes tend to have a relatively high entropic centrality when they either are embedded within a large cluster, or when they are at the boundary of two clusters (and could arguably belong to either), and moreover, (ii) sharp changes in the random walker absorption probability distribution signal boundaries of local community structures.

This leads to a two-stage clustering algorithm: First, observing that nodes at the boundary of clusters often act as hubs and have high centrality, we determine meaningful node centric local communities around nodes with low entropic centrality. This approach inherits the flexibility of the underlying centrality model, and is applicable to the spectrum of combinations (un/directed, un/weighted) of graphs. Furthermore, the strong coupling of the algorithm’s design with the aforementioned centrality measure allows to initiate the random walkers in an informed manner, in contrast to previous works based on random walks, such as [1, 4], which, in absence of any guidance on where to initiate random walks needed more complex (computationally, as well as in terms of implementation and analysis), constrained random walkers. Second, the process is reapplied on the created clusters (instead of the nodes) to effectuate a bottom-up, scalable, hierarchical clustering. Working principles behind the heuristic algorithms are supported by formal derivations, and the performance of the algorithms have been tested with experiments in terms of sensitivity and correctness, as well as through rigorous benchmarking using synthetic and real world networks with ground truth.

Finally, the existing flow based clustering approaches (and most clustering approaches, in general) do not have an inherent way to reason about the quality of clusters they may yield, given any graph. In contrast the distribution of the relative values of entropic centrality of nodes and graph centralization also inform us on whether and how much a given graph is amenable to the use of our approach for carrying out clustering.

In [23], a radically different approach (adapting [11]) for community detection is applied, where edges are iteratively removed, and in each iteration one needs to identify the edge such that the average entropic centrality over all the nodes is reduced the most. This requires the computation of entropic centrality of all the nodes multiple times for the different resulting graph snapshots from edge removals, and do so numerically over and over again. Naturally, the approach is computationally intensive and not scalable. For a specific undirected unweighted graph, our algorithm took 1.072 seconds to compute the communities, which is multiple orders of magnitude faster than the 3196.07 seconds needed by the edge removal algorithm [23] (more details on the specific experiments can be found in Subsection 4.4). The communities detected by our approach were also qualitatively better for the network where the two approaches were compared head-to-head. Moreover, the authors in [23] noted that their approach was not useful for community detection in directed graphs. We demonstrate with experiments that our approach works also with directed graphs.

To summarize, our second set of contributions are vis-à-vis graph clustering. The salient aspects of our work comprise (i) the use of entropic centrality (and underlying analysis) to inform on whether our approach will yield good quality of clusters given a graph, and if so, (ii) how to identify good candidate ‘query nodes’ around which initial sets of local community structures should be explored, which in turn yields (iii) an effective novel two-stage clustering algorithm even while using a single random walker (as opposed to prior studies, where random walkers initiated at random query nodes were shown not to be effective, necessitating more complex and constrained walks by multiple random walkers). Our clustering algorithm (iv) amortizes the previous computation of entropic centralities in computing these communities, and (v) inherits (from the underlying centrality model) the flexibility of interpreting the roles of edge weights and directionality, allowing for capturing different behaviors of a weighted directed graph as per application needs. Our approach is thus one of the few graph clustering approaches in the literature that handles directed graphs naturally, and additionally, it allows for flexible incorporation and interpretation of edge weights.

Experiments and Benchmarking: Emerging complex networks such as the Bitcoin network motivated the introduction of a framework for centrality and clustering that handles a variety of angles from which the network structures can be studied, considering in combination the direction and weight of edges. The principal objective of the proposed clustering algorithm is to seamlessly accommodate the various combinations in which the network can be interpreted. A second objective is to ensure that our approach also yields meaningful clusters in general, and in particular, that the obtained results are meaningful when applied to standard graphs used for graph clustering benchmarking. Experiments to support our work are designed accordingly.

Clustering of Bitcoin transaction subgraphs [24, 25] is performed to explore the versatility of our model vis-à-vis the spectrum of choices in interpreting the directionality and weights of edges. Since no ground truth is known, we compare the obtained results with an existing Bitcoin forensics study [32].

Evaluating in general the quality of a clustering algorithm is a debated topic [37, 30]. Complications arise because of multiple reasons, including that different clustering algorithms may identify communities which may reflect different aspects of relationships and thus different results may not necessarily be wrong or worse; there may be multiple interpretations of relationships, resulting in different ‘ground truths’ being valid. We thus report results from a variety of networks, falling into two categories: (a) synthetic networks, and (b) real world graphs with meta-information used to assign a ground truth.

We apply our algorithm on synthetically generated networks, which eliminates the ambiguity of ‘ground truth’ since it is determined by design. We refer to [17, 18] for more details advocating the use of synthetic graphs for benchmarking community detection algorithms. A caveat with using synthetic benchmark graphs is that, they may themselves be created following certain rules, e.g., [18] is generated guided by local density measures. That in turn may favor specific families of clustering algorithms. Ranging from small graphs (of 100 to 500 nodes) to larger graphs (of 1000 and 4000 nodes), the proposed algorithm fares well and is comparative with Louvain [5], with our results showing neither algorithm clearly outperforming the other in determining the clusters, but rather, each algorithm outperforming the other depending on individual instances.

We carry out comparative studies with classical networks and connect these experimental studies back to the conceptual foundations of our approach, which allow us to understand whether our approach is expected to yield good clustering results for a given graph depending on the distribution of the relative values of entropic centralities. This includes the classical karate club [38] and the small cocaine dealing network [8] to interpret and explain the meaning of our model and validate the corresponding findings guided by the well understood narrative associated with these graphs, but also the dolphin network [21] and the American football network [11], for which the performance of our clustering algorithm is compared with well known algorithms, namely Louvain [5], Infomap [34] and label propagation [2]. Remark: All experiments and implementations presented in this paper were done in Python, using in particular the libraries NetworkX [14] and Scikit-Learn [29]. All graphs were drawn using either NetworkX or Gephi [3].

A right stochastic matrix $P$ is a square matrix, where every coefficient is a non-negative real number and each row sums to 1. A right $n\times n$ stochastic matrix describes a Markov chain $X_{t}$, $t\geq 1$, over $n$ states. The coefficient $P_{u,v}$ of $P$ is the probability of moving from state $u$ to state $v$, and since the total $\sum_{u=1}^{n}P_{u,v}$ of transition probabilities from state $u$ to all other states must be 1 by definition of probability, the matrix $P$ is indeed a right stochastic matrix, called a transition matrix. To show that $P^{k}$ is again a right stochastic matrix for any positive integer $k$, take the all 1 column vector ${\bf 1}$ and notice that $P{\bf 1}={\bf 1}$ for a right stochastic matrix. Then $P^{k}{\bf 1}=P{\bf 1}={\bf 1}$. Let $(P_{u,l})_{l}$ be the $u$th row of $P$, and $(P_{l,v})_{l}$ be its $v$th column. Their product $(P_{u,l})_{l}(P_{l,v})_{l}=\sum_{l}(P_{u,l})_{l}(P_{l,v})_{l}$ determines the probability of going from the state $i$ to the state $j$ in two steps, where the intermediate state is $l$, for any possible state $l$. In general, $P^{k}$ gives the probability transition of going from any state to any another state in $k$ steps.

Consider now a connected directed graph $G=(V,E)$ with $n=|V|$ nodes labeled from $1$ to $n$ and $|E|$ directed edges, and a random walker on $G$, which starts a random walk at any given node according to an initial probability distribution. If the walker decides on which node $v$ to walk to, based only on the current node $u$ at which it currently is ($v$ does not have to be distinct from $u$), the random walk is a Markov chain, which can be modeled by a stochastic matrix $P$ where $P_{uv}$ is the probability to go to node $v$ from node $u$. We will assume that every node has a self-loop (a self-loop is needed for the model to encapsulate the case of nodes with zero out-degree.) Let $d_{out}(u)$ denote the out-degree of $u$, which includes the self-loop as per our model. A typical choice that we consider in this section is $P_{uv}=\frac{1}{d_{out}(u)}$ for every node $v$ belonging to the set $\mathcal{N}_{u}$ of out-neighbors of $u$ (this is saying that each neighbor is chosen uniformly at random). Other choices are possible, and indeed, subsequently in this paper, we shall consider the case of weighted graphs where the transition probabilities depend on the edge weights.