From Cubes to Networks: Fast Generic Model for Synthetic Networks Generation

As a first step, we generate $N$ nodes with attributes according to the $N$ samples within the cube, denoted as $V=(T,C,I)$, where $T,C,I$ represent nodes’ order, geographic and influence attributes respectively.

The following step is determining candidates of final neighbors for each node (i.e., potential neighbors). The $T$ sequence yields an arrival sequence of $V$. For each $t\in T$, let $v_{t}$ describe the corresponding node and $G_{t}=(V_{t},E_{t})$ describe the graph. The potential neighbors of $v_{t}$, denoted by $\mathit{PNbr_{v_{t}}}$, are sampled through a nearest neighbor searching algorithm, denoted by $\Upsilon(\cdot)$:

$$PNbr_{v_{t}}=\Upsilon_{k_{t}}(v_{t},V_{t-1})$$

(2)

Within $\Upsilon(\cdot)$, the number of potential neighbors (i.e., $k_{t}$) of node $v_{t}$ is determined by $v_{t}$’s influence attribute $infRt_{v_{t}}$ regardless of its geographic attribute $c_{v_{t}}$:

$$k_{t}=min(n_{t-1},\ \eta*infRt_{v_{t}}^{\theta})$$

(3)

where $n_{t-1}=\mid V_{t-1}\mid$ and $\eta,\theta\in\mathbf{R}^{+}$ are parameters guiding the global edge scale and the degree deviation among nodes respectively.

As we have discussed previously, $I$ is either pow-law or considered random. For the former, $\theta$ is set to 1, and for the latter, $\theta$ is generally between 3-9 to maintain power-law degree distribution. Once $k_{t}$ is settled, the distance measurement within $\Upsilon(\cdot)$ is obtained as:

$$d(i,j)=dist_{measure}(attr_{i},attr_{j})$$

(4)

where $i,j\in V$, $dist_{measure}(\cdot)$ represents an intended measurement, and $attr$ is the weighted order and geographic attributes:

$$attr_{i}=[\mu_{t}t_{i},\ \mu_{c}(c_{i,1},\ c_{i,2},...,c_{i,\lambda})]$$

(5)

where $t_{i}\in T$, $c_{i}\in C$, $i\in V$, and $\lambda$ being the geographic dimension. Note that the order and geographic attributes (i.e., $T$ and $C$) are both put into consideration when calculating the distance. Because in FGM, it is imperative that we fully account for the impact of both order and geographic properties on node associations (the benefit will be illustrated in Section 4.4).

As the result of neighbors resampling simply alters the recipient of connections, the only variation that can make an impact on the network’s overall properties here is $k_{t}$. This decoupling between specific algorithms and network overall properties gives more flexibility to the model. However, with different implementations leading to varied link participants, the interrelations between generated network and original data will ultimately be affected. As a result, although various implementations can be employed here, it is advised to choose according to the data under investigation.

After the potential neighbors (i.e., $PNbr$) are determined, edges are generated under the control of the influence attribute $I$.

For network $G_{t}$, let $E_{v_{t},j}=1$ indicates the existence of an undirected edge between node $v_{t}$ and $j$. The node $v_{t}$ connects to $j$ with probability:

$$P(E_{v_{t},j}=1)=\Gamma(infRt_{v_{t}},\ infRt_{j})$$

(6)

where $j\in PNbr_{v_{t}}$ and $\Gamma(\cdot)$ represents a generalized function shifting pairs of influence attributes to edge formation determinant.

In this experiment, we test whether synthetic networks produced by FGM portray intended degree distributions similar to reality. We use the term Gnode (giant node) referring to the few nodes with large degrees (i.e., the tail of the power-law distribution).

For both scenarios of FGM (see Figure 3), networks are able to exhibit power-law tendencies. Compared with other models (i.e., BA network and Configuration model) where the log-log curve gradient remains constant, the curve head of FGM is flatter than the tail, particularly in $\mathrm{FGM_{p}}$. Since the power law often applies only for values greater than some minimum $x_{min}$ for real-life networks Clauset et al. (2009), we believe our model better captures the nature of factual degree distribution (see Figure 4). The results also indicate that the larger the network scale is, the more obvious the pattern becomes.

Figure 4 shows the degree distribution of several real-life networks (i.e., a.Rozemberczki et al. (2019); b.McAuley and Leskovec (2012); c/e.Rozemberczki and Sarkar (2020); d.Leskovec et al. (2007)) and $\mathrm{FGM_{p}}$’s simulations with corresponding scales. Regardless of the field or scale of real-life networks, the actual distribution curve head is always flatter than the tail. This network property is correctly captured by our model while others cannot.

Starting here, we omit the assessment on ER networks because the randomness is too high to show observable patterns.

Another network measurement we present in detail is the average nearest-neighbor degree (ANND) Pastor-Satorras et al. (2001). As a network quantization of degree-degree correlations, ANND distribution reflects the connectivity details by specifying how connected nodes with certain degrees are. When ANND was first introduced in 2001, researchers found that the Internet in 1998 exhibited a distinct power-law ANND dependence and the same patterns have been later observed to be applicable to many other factual networks Pastor-Satorras et al. (2001); Catanzaro et al. (2005) (examples in Figure 5, a.Leskovec et al. (2005); b/c.Rozemberczki and Sarkar (2021); d.Zitnik et al. (2018); e.Rozemberczki et al. (2019); f.Cho et al. (2011)).

The ANND simulation results under different network scales show that both cases of FGM display a clear power-law ANND dependency while others remain relatively constant. To this concern, we also believe FGM outperforms others because the power-law ANND tendencies were also observed in reality.

This section provides a comparison of other network properties that help assess the synthetic networks.

Table 1 shows that, under varied scales, FGM is the only model being able to create synthetic networks with low average length paths and high clustering coefficients while still providing network variations.

Although Small-World networks process relatively high clustering coefficients and low average path lengths, their fixed edge number severely restricts model flexibility. BA networks inherit low clustering coefficients and the coefficient seems to deteriorate while the network becomes larger. The clustering coefficient measurement for the Configuration model is not applicable due to its parallel edges, making it more troublesome to measure the network density.

In this section, we demonstrate the generation time complexity of FGM by employing Locality-Sensitive Hashing (LSH) as the neighbor-searching function (i.e., $\Upsilon(\cdot$)) in Equation 2.

Generation time of a 5000-node FGM network is shown in Figure 8. The generation time complexity of FGM is solely dependent upon the process of finding $PNbr$ owing to two factors:

1. 1.

   Every node only has to consider the possibility of forming edges with a small faction of existing nodes;

2. 2.

   The determinant of edge formation (i.e., $InfRt$) is constant, circumventing the necessity of recalculation when network changes.

A constant time of finding PNbr will lead to a network generation complexity of $O(n)$, which is also the case in our demonstration of FGM with LSH’s $O(1)$ query time. This makes it possible for modeling any large-scale cubes within tolerable time as dataset scale will not accumulate the computational burden. However, it is not the case for models whose dynamics are dependent on the ever-changing network properties because of the need for recalculation. Here, we compare the time complexities of different models.

We believe the comparison of proportional time costs is much more suitable than the absolute time costs. With the very nature of network models being several pre-defined regulations, varied implementations of the same model will alter the time cost to a great extent. Still, if compared to the time cost of a small network, the proportional time costs of bigger networks will still reflect the model’s tolerance of large-scale data.

Thus, every model’s generation time of a 1000-node network is denoted as {1000} uniformly beforehand. We also include the OSN Evolution model Khan and Lee (2018b) which, like FGM, models data into networks.

Table 2 shows that within the field of scale-free networks, the Configuration model, BA model Atwood et al. (2015), and FGM process linear generation time complexities. As for the other data-driven approach, the OSN Evolution model becomes extremely time-consuming as the scale gets bigger.

In this section, we provide evaluations of FGM from a macro-perspective analysis, i.e., properties of interrelated networks from various cubes. We convert previously illustrated cubes in Figure 2 to interrelated networks and further investigate whether synthetic networks can reproduce typical patterns as real-life networks while, in the meantime, reflecting patterns of original cubes.

From Table 3, it is clear that, regardless of cube sizes, FGM synthetic networks can maintain high clustering coefficients with low average path lengths as factual networks. Figure 9 shows the degree distributions exhibit power-law patterns. Notably, when examined in conjunction with the $I$ distribution of the original cubes, these degree distributions also accurately capture the uniqueness of the original patterns, that is, the manner in which the data points are distributed in the plot.

Now, from a macro-perspective analysis, we believe that FGM can generate synthetic networks with interrelations to reality, where common properties of factual networks are reproduced and original data patterns are preserved to a certain degree.

Here, we present the evaluations of FGM from a micro-perspective analysis, i.e., how the Gnode (i.e., 9-11 attack) in Global Terrorism Database (GTD) START (2020) reflects the prescribed influence decay phenomenon (see Section 4.4). To elaborate, we compare the edge dynamics of 9-11 attack in FGM and BA network of modeling GTD between 2001 and 2005.

Figure 10 shows that, in FGM Gnode 9-11’s degree remained stationary after around 3 months whereas the edge dynamic in BA network kept evolving throughout the simulation. That is to say, the 9-11 influence on other attacks in FGM eventually decays despite its enormous impact at the time, whereby, in property-based model like BA Network, the impact keeps growing. To make things worse, 9-11 is forever the biggest node for each new arrivals no matter how the world evolves. Nowadays clearly more recent events have bigger impacts.

From a micro-perspective analysis, we also believe FGM reflects factual phenomenon to a centain degree where previous works cannot.