The understanding of how the complex systems governing various domains, from social interactions to financial transactions, is closely connected with our comprehension of their underlying dynamic networks and their evolution patterns. In particular, the evolution of these networks provides insights into the underlying mechanisms driving their changes, which can be pivotal for applications such as node segmentation, prediction of future states, and role discovery. Among the various approaches to studying network evolution, graph evolution rules (GERs) stand out since they produce human-readable outcomes without requiring any pre-assumptions about the underlying evolutionary mechanisms. In this work, we leverage GER to derive evolutionary node profiles (NEPs), capturing the distinct patterns of how nodes change over time within the network. These profiles allow us to identify groups of accounts characterized by similar evolution rules, revealing common interaction patterns. As a case study, we apply our approach to Sarafu, a complementary currency platform following the Web3 paradigm, which ofers rich temporal economic data. Sarafu represents a contemporary human complex system that integrates humanitarian aid, collaboration, and financial aspects. By analyzing Sarafu's network using our GER-based method, we identify two distinct evolutionary traits, uncovering significant behaviors that contribute to the platform's operation. Our findings suggest the efectiveness of using graph evolution rules in real-world dynamic networks, showcasing their potential to enhance our understanding of the node-level dynamics of complex systems.
Studying the evolution of real-world dynamic networks is critical for understanding complex systems
that span various domains, from social interactions to financial transactions. The temporal dynamics of
these networks can reveal underlying mechanisms driving changes and enabling applications such as
anomaly detection, prediction of future states, and role discovery. Traditionally, models, mechanisms,
and metrics have been introduced to interpret how dynamic networks grow and evolve, often assuming
that their growth is governed by a unique parameterized mechanism, such as preferential attachment
or triadic closure [
CEUR Workshop
ISSN1613-0073
In this work, we embrace the ego-networks viewpoint for the analysis of temporal networks but rely
on graph evolution rules (GERs) rather than dynamic graphlets [
We showcase the potential applications of NEPs on transactional data from the Sarafu platform.
Sarafu is a digital complementary currency platform developed by Grassroots Economics to facilitate
mobile payments and distribute humanitarian aid in Kenya, and is representative of a vast landscape
of applications based on the Web3 paradigm [
To sum up, the representation of the dynamics within ego-networks using GERs ofers a potential tool for uncovering and understanding the intricate patterns of interactions in complex temporal networks. By leveraging GERs, we can gain insights into how individual nodes and their immediate neighborhoods evolve, providing valuable information for applications such as node segmentation, prediction of future network states, and role discovery. This approach not only enhances our comprehension of the underlying mechanisms driving network changes but also supports the development of more accurate models for analyzing and predicting the behavior of real-world dynamic systems.
In this section, we provide a brief background on the frequent graph mining approach we use to characterize the dynamics of ego-networks, and we summarize the related works on networks and node representation based on (temporal) subgraphs, as well as works about our case study: Sarafu, the complementary and humanitarian aid crypto-currency.
Graph Evolution Rules - GER. Our approach to describing dynamics in temporal ego-networks is
mainly rooted in graph evolution rules. GERs mining is a frequency-based pattern discovery method
that allows analyzing the evolution of temporal networks. The goal of graph evolution rules (GERs) is to
discover frequent local changes occurring repeatedly throughout the network evolution [
t0 t1
GERs are a powerful method that can enable the development of more accurate network evolution
models for predicting future network changes, or be used to distinguish them from other graphs, whose
evolution is governed by diferent mechanisms. State-of-the-art methods focused on detecting the
t t t
topological evolutionary mechanisms share t0he same two-step metho1dology: first, they extract2rules via
frequent subgraph mining, and then they filter the output using quantities such as the support and/or
confidence measures. In the literature about GERs, one of the first methods is GERM, developed by
Berlingerio et al. [
Node representation based on (temporal) subgraphs Recent advancements in node vectorial
representation have leveraged frequent subgraphs, motifs, and graphlets to enhance the richness of
temporal graph embeddings. One notable approach is the Neural Temporal Walks (NeurTWs) [
From a node-centric perspective, our main aim is to represent nodes based on the mechanisms that characterize the evolution of the interactions surrounding them. The methodology to get this kind of representation is based on two main tasks: a) the extraction of the ego-networks from the overall temporal network describing the system, i.e., interactions surrounding every single node; and b) the identification of the mechanisms/rules driving the evolution of each ego-network through the computation of the graph evolution rules. In this section, we detail these two main tasks and propose a vector-based representation for nodes, rooted in graph evolution rules, namely the node evolutionary profile - NEP .
In this work, we model the set of interactions or transactions among the members of a networked system following the broad definition of temporal network = ( , ) proposed in [26, 27], where: • is the set of users in the system; and • = {(, , ) | ∈ [1, ], (, ) ∈ × } is a set of timestamped directed links (, , ) . Each link corresponds to an interaction/transaction from node to user that occurs at time . By the temporal network definition, we cover both repeated interactions between pairs of nodes, or unique interactions, leading to the formation of growing networks, i.e., a first approximation of the evolution of online social networks, for instance.
To accomplish the first task, we extract the temporal ego-network of a generic node from the temporal graph . For each node , its ego-network () = ( , ) corresponds to the temporal subgraph induced by ’s neighborhood, including itself. Formally, the set of nodes is defined as = ∪ Γ() where Γ() is the neighborhood of node . The set of edges is defined as = {( , , ) | ( , , ) ∈ , ∈ , ∈ }, i.e. all temporal links whose endpoints are in . The extraction of temporal egonetworks leads to the creation of a set of small temporal subgraphs that can facilitate a parallelization of node-centric analyses.
To deal with the second task, i.e., identifying the graph evolution rules characterizing a temporal
ego-network of a node, we rely on the EvoMine algorithm [
22
11
21
(a)
(b)
(c)
state-of-the-art algorithms for GER extraction, such as GERM [
Topological constraint of rules. The main characteristic of the evolution rules returned by Evomine
is their focus on changes between two consecutive timestamps, i.e., rules describing how a
precondition subgraph will evolve into a postcondition subgraph in the very next future (next timestamp or
snapshot), ensuring that any modifications specified in the postcondition occur immediately, following
the timestamp of the precondition’s edges. In EvoMine a rule ∶ ( , ) is valid whether: i) ,
i.e. the set of nodes of , matches ; ii) ≠ or ℓ ≠ ℓ , ensuring evolution — at least a
change between consecutive timestamps; and iii) the union graph of ( , ) must be connected, to
guarantee the rule captures a localized process. In particular, the union graph ( 1 ) corresponds to a
merging of the graphs in a graph sequence 1 = ( 1, … , ) with = ( , , ). The merging results in
a labeled static graph that includes the same set of nodes and the union of all edge sets , ∀ = 1 … .
Through the merging, we assign labels to nodes and edges by concatenating the labels of all timestamps
included, thus encoding the temporal evolution. An example of a union graph obtained from the graph
sequence in Figure 2a is reported in Figure 2b. Here, the label 21 for the pink node indicates that the
node had label 2 in , and label 1 in + 1 . Similarly, the label assigned to the link connecting the pink
and orange circled nodes - 1 - indicates that the link was not in , but was present at +1 .
The algorithm. The union graph is the main input of the EvoMine algorithm. Indeed, the algorithm
applies a frequent connected subgraph mining method (Gspan [
Event-based support. A further advantage of Evomine is that it provides two types of support measures: (i) an embedding-based support, i.e., the minimum image-based support, and (ii) an eventbased support. In our pipeline, we adopt the second type of support, which states that the support of a rule is determined by the total number of change events that include the rule. In the event-based setting, the input for Gspan is a set of event graphs, i.e., a subgraph of the union graph ( +1 ) induced by the event neighborhood. The event neighborhood is defined as the neighborhood of the node(s) involved in the node or edge event1. Finally, the event-based support ( ) of a rule is the number of event graphs in the overall set of event graphs that contains the union graph of as a subgraph.
For example, given the snapshots and + 1 of a temporal graph as the one depicted in Figure 2a, we obtain its union graph ( +1 ) reported in Figure 2b. If we consider the creation of the edge between and as the target event, the corresponding event graph is the subgraph induced by , , and its neighbors (depicted in Figure 2c).
Algorithms parameters. The outcomes of EvoMine are mainly influenced by two parameters. The
ifrst one is the support , which specifies the support threshold for rules to be included in the output, and
allows us to discard rare evolution patterns. The second crucial parameter is the maximum number of
edges allowed in the union graph of any rule in the output, and impacts the complexity of the evolution
rules. Details about the selection of the parameter for the specific case study are reported in Section 5.
Scaling strategy. We adopt a few parallelization strategies to scale the method to relatively large
temporal networks that may span long periods. First, the computation for each node can be parallelized
since each ego-network can be extracted and treated independently. However, this may not be enough
since computational times increase with the length of the sequence graph. To cope with this issue,
we rely on how EvoMine computes the event-based support: the support for each rule is computed
across consecutive timestamps (event graphs) in a pairwise manner, and then the results for each
pair of consecutive snapshots are aggregated. This approach is not available through the original
implementation, but it can be run in parallel by applying EvoMine on each pair of consecutive timestamps
in the timespan { 1, 2, … }. This parallelization strategy asks for a precaution since each application of
EvoMine independently generates rules (with edge lists and support) whose identifiers are not unique
across diferent pairs of snapshots - a canonical form to identify isomorphic patterns across the various
outputs is missing. To deal with this issue, and efectively aggregate the supports of a rule across
timestamps, we integrate into the algorithm an isomorphism check which assigns a unique identifier to
classes of isomorphic temporal pattern [28]. In this way, despite the external parallel and independent
execution, the results remain comparable in the aggregation. Finally, we introduce a further check
in the parallelization strategy to apply the computation of the support only on pairs of consecutive
snapshots that contain at least a link insertion event. For example, if in a temporal network, only
the timestamps = [
In static and temporal networks, the distribution of measures based on static and/or temporal subgraphs
of diferent order and size has been used for encapsulating the static and dynamical signature from
both a network- and node-level perspective. In this sense, the graphlet-degree vector in [29] and its
extension to the temporal setting given by the dynamic graphlet degree vector [
We denote the vector representation as Node Evolutionary Profile - NEP , and it represents the distribution of the graph evolution rules for the ego-network () of the node . The construction of the node evolutionary profile is based on the graph evolution rules and their supports computed by EvoMine on each ego-network () ; while a vector representation common to all nodes is supported by the unique and common identifiers for rules based on the canonical form (see the paragraph on ”Scaling Strategy” in Section 3.2). Specifically, each element of the Node Evolutionary Profile ()
is defined as follows: () = ∑=1 ( ) ( ) (1) where
( ) is the event-based support of the rule in the ’s ego-network and is the number of distinct GERs identified by EvoMine on the whole set of nodes. In short, given an ego-network of a node , its NEP represents a signature of its evolution as well as a compact representation based on the dynamics of the interactions among the neighbors of and with the neighbors and .
Our work on node temporal behavioral representation using graph evolution rules considers as a
case study a transaction network in the Web3 landscape: the Sarafu network. Sarafu2 is a digital
complementary currency token developed by the Grassroots Economics (GE) foundation3. This platform
enables users to make payments via mobile phones by transferring Sarafu tokens to other registered
users. The Kenyan Red Cross leveraged Sarafu tokens to distribute humanitarian aid during the
COVID19 pandemic [
Data Collection and features.
As collected by [30], the Sarafu dataset provides comprehensive and anonymized data on token transactions and user characteristics from January 2020 to June 2021. The dataset — a quite unique playground in the field of temporal graph analysis, mining, and machine learning — encompasses a total of 412,050 economic transactions involving 40,343 users. Each transaction includes anonymized IDs for its source and target, representing the sender and receiver of cryptocurrency tokens. Additionally, the transaction weight, indicating the number of tokens transferred from source to target, is recorded. Critical for this study is the timestamp, detailing the precise date and time of each transaction down to milliseconds. Since the millisecond temporal granularity would result in a huge set of extremely sparse snapshots, making the application of EvoMine unfeasible, we aggregate timestamps into a daily granularity. As for information on user profiles, data include attributes such as business type (user-provided standard categorization), geographical information about the user’s residence, and a distinction between beneficiaries (regular users) and group accounts. This latter distinction between regular and group accounts is fundamental in the remainder of the paper since it allows focusing only on token transactions capturing value exchanges for the communities and not transactions useful only for the functioning of the platform.
Relevance to temporal behavioral representation.
The rich temporal data contained within the Sarafu dataset makes it an ideal case study for applying our dynamic graph evolution rules approach. The dataset represents a contemporary human complex system that integrates humanitarian aid, collaboration, and financial aspects. By analyzing this dataset, we aim to capture and characterize the temporal behavioral patterns of nodes within this transaction network, providing insights into the dynamics of digital currency exchanges in a humanitarian context. 2Sarafu means “currency” in Swahili 3https://www.grassrootseconomics.org/pages/about-us.html 1.0 0.8 0.6 F D C 0.4 0.2 0.0 ego-networks size filtered ego-networks size 80th percentile 0
We applied the described methodology to the Sarafu transaction network, limiting our attention to economical exchanges among regular users and between regular users and group accounts. Through Node Evolutionary Profiles (NEPs) we point out interesting insights into the dynamics of ego-networks. By identifying distinct interaction patterns and traits, we showcase the eficacy of NEPs in capturing temporal behaviors. The results highlight two primary evolutionary traits within the network that can be extracted by clustering NEPs. This analysis of Sarafu serves as a showcase of the potential applications of NEPs on temporal networks — especially networks reconstructed from Web3 platform data — demonstrating their capability to uncover the dynamics of ego-networks in complex transactional networks, which can be extended to various other domains and contexts.
The extraction of the ego-networks from the original transaction network of Sarafu has returned 40343 ego-networks, which were reduced to 16030 after applying the filter on consecutive snapshots (see Section 3.2). This important reduction in the number of valid ego-networks indicates that more than half of the accounts do not show interactions with and among their neighbors in consecutive timestamps4. First, we investigate, for each ego-network, the number of included interactions to assess if, even in this case, this quantity shows a heavy-tail trait like most of the phenomena concerning real-world networks and human dynamics [31]. To this aim, in Figure 3 we report the cumulative distribution of the number of interactions (ego-network size) in each ego-network. The distribution of the ego-network size (red curve) is skewed, with the majority of nodes having very few interactions within their ego-networks. This observation may impact the outcomes of our analysis since if the temporal subgraph from which we identify the evolutionary profile is too small, it does not have enough data to actually describe the temporal behavior of a node. For this reason, based on the distribution, we only consider nodes whose ego-network presents at least 116 interactions, corresponding to the 80ℎ percentile of the ego-network size distribution, shown in Figure 3 by the blue dotted line. Thus, we obtain 3207 ego-networks, whose size distribution is depicted in Figure 3 with a green line. In short, the analysis of ego-network sizes allowed us to identify the most significant accounts in the Sarafu networks in terms of transaction activity, and at the same time, it highlighted that most economic activities are handled by a small 4We are aware that the reduction of ego-network is quite important, but not applying the filter on consecutive timestamps would have altered the dynamics within ego-networks. portion of the accounts in the system. 5.2. NEPs After the preprocessing and filtering phase, we apply the EvoMine algorithm to the 3207 ego-networks. In particular, we fixed 1 as the minimum support — the algorithm returns all the graph evolution rules in the graph — and a maximum number of three edges per pattern, using the event-based support. As a result, after applying the general mapping procedure, we obtained 40 diferent graph evolution patterns, which correspond to the dimensions of the node evolutionary profiles. We collect all the NEPs by stacking them into a matrix, and we visualize them through a heatmap, where rows represent ego-networks and columns indicate the IDs of the graph evolution rules. The matrix of all the NEPs is displayed in Figure 4. From a column-wise inspection, we observe that in general, only a limited set of graph evolution rules characterizes the dynamics of the transactions in ego-networks. Indeed, only rules 0, 1, 2, 3, 4, 10 and 15 show high frequency values, with the first rule ( 0) being the most frequent for many ego-networks.
We report these frequent GERs on the right side of Figure 4. We note that six out of seven rules (0, 1, 2, 3, 4, 15) describe star- or chain-like expansions starting from an empty precondition, while rule 10 expresses transactions that become reciprocal in just one day. The reciprocal rule may represent a distinctive trait of the Sarafu, since it mirrors the cooperation among the members of local communities. In this case, it is worth noting this cooperative behavior actualizes in only a day. Moreover, from a data perspective, the skewed distribution of rules points out that it is very likely that if we reduce the dimensionality of NEPs, most of the information in the data will remain. On the other side, from a row-wise inspection, we observe a certain level of variability in NEPs, so there is not a common trait characterizing the dynamics of the interactions in ego-networks, even if a few representative traits are identifiable.
The analysis of NEPs has pointed out two principal observations that are fundamental for showcasing how NEPs can be exploited for data discovery tasks: i) only a few GERs are frequent in NEPs; and ii) NEPs are varied but with a limited level of variability. Based on these observations, we focus on identifying a few classes that may represent dynamic traits of ego-networks’ evolution in Sarafu. We apply a clustering pipeline on the NEP matrix to identify these possible diferent traits. Taking advantage cluster 0 cluster 1 t0 (c) t1 F(iag)ure 5: In a) The Calinski-Harabasz score as (abf)unction of the number of clusters returned by the ag(gcl)omerative clustering algorithm. The highest CH-score corresponds to = 2 , i.e., two clusters. In b) NEPs are visualized in 2 dimensions with points and colored according to the membership of one of the two clusters. To visualize NEPs in a 2D space we ran dimensional reduction (PCA) on the two principal components. In c) the NEP centroids of the two clusters, along with the most frequent, on average, GERs. GERs are represented through the compact visualization in Figure 1. of the first observation on NEP dimensions, first, we performed dimensionality reduction by Principal Component Analysis (PCA) to reduce NEP dimensions while preserving most of the information in the NEP matrix; then we ran a hierarchical clustering algorithm on the transformed NEPs to identify groups of ego-networks showing the same evolutionary trait. As for the PCA algorithm, we selected the number of components using the explained variance ratio: fixing a cumulative percentage of explained variance to 0.99, we still halve the dimensions from 40 to 24, finding a lower-dimensional representation of NEPs that is still informative as the original one.
The transformed NEPs feed an agglomerative clustering algorithm using Ward as the linkage strategy since it is less sensitive to noise and should return more even clusters in terms of size. When using agglomerative clustering, one has to select the best value for the number of clusters , a fundamental parameter not known a priori that must be fixed before running the algorithm. In this case, we select as the value that maximizes the Calinski-Harabasz (CH) score of the agglomerative clustering by varying from 2 to 14 with step 2. The Calinski-Harabasz (CH) index assesses clustering performance by comparing the variance between clusters to the variance within clusters: a higher CH score indicates compact and well-separated clusters, suggesting a more optimal clustering configuration. According to the trend of the CH scores reported in Figure 5a, we choose = 2 . Thus, there are two main traits characterizing the dynamics of the transactions occurring within ego-networks, and consequently, two groups of accounts. In Figure 5b we display these two groups of accounts in a 2D representation returned by applying PCA, while in Figure 5c we report the centroids of the two clusters to highlight the diference between the two prototypical behaviors. In particular, we note that the average behavior characterizing the dynamics of the interactions in ego-networks of accounts belonging to the cluster 0 is dominated by the rule 0 - the creation of a single link at time + 1 when the precondition is empty - which on average accounts for the 20% of the rules involved in the dynamics of ego-network. The remaining rules also characterize the cluster 1, but on average, they are spread more uniformly than in cluster 0. In short, the dynamics of transactions in the ego-networks of the accounts in the first clusters are mainly driven by star- and chain-like expansion rules that appear in a successive timestamp without a precondition, where the appearance of a single link is dominant; on the contrary, the dynamics in the second cluster are more homogeneous even if they lead to the same kind of expansion rules. The most important graph evolution rules are the same, while it is the rule frequency that diferentiates the two dynamic traits.
Given these two traits and the networked nature of our dataset, we finally wonder if accounts that usually interact by exchanging transactions are characterized by the same rules describing the dynamics of their ego-networks. To cope with this question, we first proceed by computing a static projection — graph flattening — of the graph sequence describing the Sarafu temporal network, then we compute the assortativity of the network using the clusters returned by the clustering algorithm as a categorical attribute. In detail, in the static projection, two accounts are connected if they interact at least once during the observation period, and the directed links are weighted according to the number of transactions sent by the source node toward the target node. Moreover, the construction of this graph is limited to the 3027 accounts in the analysis since the cluster attribute is missing for the remaining accounts. In this setting, the attribute assortativity is 0.590 and indicates a tendency for accounts to interact with other accounts that have a similar ego-network dynamic. In general, we stress the fact that by utilizing node evolutionary profiles, it is possible to develop applications that highlight properties and relationships between accounts based on the dynamics of the extracted ego-networks.
In this study, we introduced a method for representing ego-network dynamics through subgraph-based evolution rules, enabling a nuanced analysis of temporal behaviors within networks. Applying Node Evolutionary Profiles (NEPs) to the Sarafu transaction network revealed significant insights, identifying two main interaction traits: one dominated by the single-link expansion over other star- and chain-like expansions, and another with a more homogeneous distribution among the same expansion rules.
These findings underscore the potential of NEP-based representations to reveal underlying behavioral patterns in complex networks. Analyzing ego-network dynamics with graph evolution rules supports various applications, such as distinguishing user behaviors in financial transaction networks like Sarafu, crucial for operational improvements and strategic decision-making. Beyond identifying behavioral traits, the NEP-based approach enhances the understanding of interaction dynamics, aiding in the development of applications that highlight the properties and relationships between accounts.
MZ ang SG are partially supported by PRIN 2022 Project ”AWESOME: Analysis framework for WEb3 SOcial MEdia” (2022MAWEZA - H53D23003550006, G53D23002900006). MZ, SG and CQ are partially supported by the project SERICS (PE00000014), under the MUR National Recovery and Resilience Plan funded by the EU - NextGenerationEU.
During the preparation of this work, the author(s) used Grammarly in order to: Grammar and spelling check, Paraphrase and reword. After using this tool/service, the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content. preprint arXiv:2207.08941 (2022). [24] C. T. Ba, A. Galdeman, M. Zignani, S. Gaito, Temporal analysis of cooperative behaviour in a blockchain for humanitarian aid during the covid-19 pandemic, in: Proceedings of the 2022 ACM Conference on Information Technology for Social Good, 2022, pp. 292–299. [25] C. T. Ba, M. Zignani, S. Gaito, Cooperative behavior in blockchain-based complementary currency networks through time: The sarafu case study, Future Generation Computer Systems 148 (2023) 266–279. [26] X.-X. Zhan, C. Liu, Z. Wang, H. Wang, P. Holme, Z.-K. Zhang, Measuring and utilizing temporal network dissimilarity, arXiv preprint arXiv:2111.01334 (2021). [27] P. Holme, J. Saramäki, Temporal network theory, volume 2, Springer, New York City, NY, 2019. [28] A. Galdeman, M. Zignani, S. Gaito, Unfolding temporal networks through statistically significant graph evolution rules, in: 2023 IEEE 10th International Conference on Data Science and Advanced Analytics (DSAA), IEEE, 2023, pp. 1–10. [29] T. Milenković, N. Pržulj, Uncovering biological network function via graphlet degree signatures,
Cancer informatics 6 (2008) CIN–S680. [30] W. O. Ruddick, Sarafu Community Inclusion Currency, 2020-2021 uk data service reshare, 2021.
URL: https://reshare.ukdataservice.ac.uk/855142/. doi:10.5255/UKDA- SN- 855142. [31] M. Karsai, H.-H. Jo, K. Kaski, et al., Bursty human dynamics, Springer, New York, NY, 2018.