{'fraction_non_alphanumeric': 0.031153767193594743, 'fraction_numerical': 0.012369123383288853, 'mean_word_length': 4.764792899408284, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Caterpillar Quota Walk Sampling: A New Predictive Sampling Method for Spread Models in Networks

Network sampling identifies a subset of nodes and/or edges from a network, producing an induced graph. Exploration-based sampling algorithms grow the induced set from an initial node by iteratively traversing and accumulating unvisited neighboring nodes from the original network. Many exploration-based sampling algorithms suffer drawbacks that limit the sum of degrees of visited nodes and thus the number of high-degree nodes visited. Furthermore, a strategy may not adapt adequately to volatile degree frequencies throughout the original network architecture, which influences how deep into the original network an algorithm could sample. This paper proposes a novel, exploration-based network sampling algorithm called caterpillar quota walk sampling (CQWS) inspired by the caterpillar tree and is compared to four other algorithms. CQWS generates a spread model as its sample by visiting the highest-degree neighbors of previously visited nodes. For each previously visited node, the top proportion of highestdegree neighbors creates the next set of caterpillar trees. Tunable and trainable parameters allow CQWS to maximize the sum of the degrees of the induced graph from multiple trials when sampling dense networks. Test scenarios included both sparse and dense networks evaluated over all the algorithms. Results show CQWS performance was best over dense networks. Evaluating the degree sum results, CQWS consistently outperformed other algorithms when sampling both sparse and dense networks.


Introduction
Complex networks abundant within different community structures have far-reaching applications in modeling complex systems such as social media circles, food webs, international trade, and the World Wide Web (Ribeiro & Towsley, 2010). Theoretically, a network is synonymous with a graph from graph theory. This paper defines a network = ( , ), a nodes (vertex) set , and edge set . Each edge connects and establishes some relationship between two nodes in . This definition specifically pertains to a simple undirected network, which is studied in this paper. For various applications, a node may present a social media account, a port in a shipping network, or cells in a biological network (Maiya & Berger-Wolf, 2010). An edge often stipulates a specific type of connection between two entities represented by nodes. For example, an edge may represent the strength of an activation potential across two neurons, the internet connection between two servers, or the status of social media connections (followers and friends). Depending on the application, both nodes and edges may carry qualitative and quantitative attributes to fulfill the network model's purpose. As opposed to regular graphs such as lattices and tessellation-based graphs, networks that model real-world phenomenon can have high variations in edge density, node density, clustering density, and other quantifiable attributes that delineate community structures throughout the entire network (Ribeiro & Towsley, 2010).
Network sampling establishes one way to analyze and mine a vast network for meaningful data. By excising a smaller subset of nodes and edges, executing algorithms and other computations on a representative subgraph eliminates computational and scalability constraints faced by the original network. Random sampling from statistical experiments can be conceptually transferred to network sampling as random node (RN) and random edge (RE) network sampling algorithms. For a budget of n nodes in a sample, RN selects n random nodes from , while RE selects enough edges from until the number of unique endpoints of edges (nodes) equals n (Ribeiro &Towsley, 2010).
However, large networks seldom have all nodes and edges initially accessible or at least feasibly reachable (Rozemberczki et al., 2020b). A common reason is saving extremely large networks in relatively slow-acess storage mediums.Furthermore, organizations use systems with limited memory and therefore can only load and view a small proportion of a stored network.
This renders RN and RE unusable. Since a relatively small subset of is feasibly accessible, sampling algorithms using graph traversal from already available nodes offer a more viable solution. Futrhermore, such exploration-based sampling algorithms can generate a sample proximal to specific nodes of interest. For example, if a new business seeks a location to set up shop, examining nodes (i.e. locations) close and reachable to nodes of interest (i.e. consumer communities) facilitates choosing the optimal location. The quality of sampled nodes can be evaluated by a metric that summarizes connectivity, clustering, degrees, or other characteristics of the sample. Many algorithms follow this general heuristic of starting at a single node and iteratively adding unvisited nodes in adjacent to nodes already in the sample (Rozemberczki et al., 2020b). To compare different exploration-based sampling algorithms, establishing some time or resource bound per sample creates an even field for comparisons. In this paper, a fixed sample size n is the bound, setting = . The network sampling algorithms in this study are inspired by spread models from a network context. Conceptually, a spread model can simulate the spread of influence or flow of information from node to node (Kuikka, 2018). In a network, a spread model is simply an induced subgraph ⊆ produced by traversing nodes from initial node .Across many applications, node degree constitutes a value of interest. The degree of a node , symbolically deg( ), is defined as the number of adjacent nodes to . The set of adjacent nodes to is the neighborhood of , symbolically ( ). Applying the concept of a spread model delivers insight on how to reach the highest-degree nodes proximal to s.
Two problems current exploration-based network sampling algorithms face are addressed in this paper. First, targeting high-degree nodes in S was not deeply addressed during the development of many sampling algorithms (Rozemberczki et al., 2020b). In many real-world applications, node degree constitutes a value of importance (Rozemberczki et al., 2020b). Actual meaning ranges from someone's social circle to the number of highways intersecting a city.
Targeting high-degree nodes provides direct benefit when sampling networks that model these applications. Second, a network sampling algorithm may linger in proximity to the start node rather than reach nodes farther away (Rozemberczki et al., 2020b). This renders a weaker representation of and forfeits opportunities to discover higher degree nodes farther away from . Therefore, a larger spread of edge distances between sampled nodes and indicates greater reachability by a tested algorithm.
This paper proposes a novel algorithm that attempts to fix these two issues. Caterpillar Quota Walk Sampling (CQWS) selects new nodes by degree. For each previously visited node , unvisited neighbors in ( ) that rank at or above a certain percentile by degree are visited. At each iteration, each newly visited node branches into new caterpillar trees rooted at . Sample thus becomes a lobster graph constructed from recursive branching of caterpillar trees off one another. Four other exploration-based sampling algorithms besides CQWS are analytically compared in performance regarding the two aforementioned problems,discussed in the Preliminaries section. definition 8: A caterpillar tree is a tree that requires every vertex to be within 1 edge of a central path.

Definitions and Notations
definition 9: A lobster graph is a graph such that can be transformed into a caterpillar tree after removing any set of leaf nodes. ( ) with uniform probability (Li et al., 2019). SRW naturally predisposes bias towards higher degree nodes. However, the lack of any optimization criteria limits SRW on how to visit the next node.
common neighbor aware random walk sampling. A variant of random walk samplers, the common neighbor aware random walk (CNARW) focuses on reaching nodes less likely to be visited by SRW. For each previously visited node , a random number | 0 < < 1 is selected.
where is the number of common neighbors between u and v (Li et al., 2019). A common neighbor to and is any node adjacent to both and . The developed strategy helps the algorithm traversefrom s faster than SRW. This makes the distance distribution of less likely to be constrained to a small value.
snowball sampling. Snowball sampling expands outward with a new layer of visited nodes per iteration. For ∈ ℕ, each node from the previous iteration selects k adjacent, unvisited nodes (Goodman, 1961).a random subset of ( ) with size is selected following a uniform probability distribution (Heckathon, 1997 operates as a group of dependent SRW traversal operations (Ribeiro & Towsley, 2010).
Suppose that queue contains nodes in , symbolically ( 1 , 2 , … , ). Select one node ∈ with probability deg( ) Σ ∀ ∈ deg( ) where. Replace u with any neighbor ∈ ( ) and repeat the process until the sample reaches the required size (Ribeiro & Towsley, 2010). As a probabilistic algorithm, the node in with maximum degree is most likely, but not guaranteed, to be visited over another node with lesser degree. Since FS essentially acts as RWS distributed across separate sampling processes taking turns, this algorithm is omitted from the experimental procedure for redundancy.
The time complexity of each algorithm from the experiment is given in Table 1. The time complexity is focused on each visited node during each iterative step rather completion of a sampling.

Proposed Method: Caterpillar Quota Walk Sampling
CQWS expands the graph, incorporating additional nodes by selecting from the upper end of ( ), where v represents each node visited in the previous iteration. The selection criteria depends on two thresholds 1 and 2 where 0 < 1 < 2 < 1. During each iteration, CQWS partitions ( ) into two halves and selects the largest possible subset 1 from ( ) such that Σ ∈ 1 deg( ) ≤ (Σ ∈ ( ) deg( )) * 1 . Repeat this division of ( ) into two halves, but a larger subset of highest nodes in ( ) named 2 are selected such that Σ ∈ 2 deg( ) ≤ (Σ ∈ ( ) deg( )) * 2 . Remove any nodes from 2 already in 1 .More concisely, 2 ≔ 2 \ 1 is executed after initially filling the 2 quota. In synopsis, 1 and 2 fulfill quotas for two consecutive groups of nodes in ( ) such that Σ ∈ 1 deg( ) Σ ∈ deg( ) < 1 and Σ ∈( 1 ∪ 2 ) Σ ∈ < 2 . Each iteration,each node ∈ ( 1 ∪ 2 ) joins sample S. However, nodes in 2 become inactive for future iterations and their neighbors do not undergo the algorithm. While each node in 1 that each branches into new caterpillar trees, each node in 2 becomes an endpoint of a permanent 1edge offshoot from its parent node . Figure 3 compacts the proposed algorithm into pseudocode.

Methodology
The hardware used for this work consists of 10 th generation Intel i7 core and 16 GB of RAM, and computations were executed on a WSL Ubuntu 20.04 terminal. All code was written in Python version 3.8.5. To evaluate each algorithm, two synthetically generated randomnetworks, 1 = ( 1 , 1 ) and 2 = ( 2 , 2 ) , were sampled. Each network is a gnm random graph, a variant ≔ ∪ REPEAT UNTIL | | = of Erdős-Rényi graph. Each network is a random selection out of all possible networks with n nodes and m edges. The parameters for 1 are = 1000, = 5000 and 2 are = 1000, = 500000, respectively. With equal node count, the disparity in the number of edges by a factor of | 2 | | 1 | = 100 contrasts the performance of algorithms between sparse and dense networks. Initially, SnowballSampler and CaterpillarQuotaWalkSampler instances have undergone parameter tuning (Rozemberczki et al, 2020b;Qin, 2020). Each algorithm exceptCQWS was executed on 1 and 2 via instances of classes from the Python library littleballoffur (Rozemberczki et al, 2020a). Each sampling algorithm per network had been evaluated with two scoring metrics, degree sum and distance variance, yielding a total of four sampling executions per algorithm per metric per network. Scores are reported as a 4 × 2 tables, namely Table 1 and Table 2 under Results. The tables correspond to sampling on 1 and 2 , respectively.
Scoring Metrics degree sum. This is the frequency, or hit rate, of high-degree nodes. Since the exact degree dividing high-degree and low-degree nodes is subjective and application-specific, the sum of degrees for all sampled nodes, Σ ∈ deg( ), is employed as a holistic, application-agnostic measurement to indicate how strongly an algorithm targets higher degrees. distance variance. This evaluates the spread of nodes in by computing the distance variance ( ( , )), where ( , ) is the edge countin any shortest path between and . The term "distance" here thus generally refers to the minimum edge count between any sampled node and . This gauges how deep an algorithm can reach into from . Other statistics such as the mean, median, and mode may also convey the reachability of an algorithm. However, the variance is a more stable and more representative option than the three aforementioned point estimates. The mean is susceptible to outliers, as a sampled node extremely far from s gives an inaccurate value of the true center of distances. The median, although more robust against outliers than the mean, is determined by the ordinal position of the middle element in the distance distribution andfails to measure the spread of distances. . Similarly as a point estimate, the mode also does not incorporate the distances of all sampled nodes and does not capture the spread of distances. Compared to the three aforementioned metrics, computing the variance accounts for all values in the distance distribution and retains consistency across multiple trials.

Parameters for snowball sampling and CQWS have each been tuned by an
NetworkSamplerTuner instance from NetworkSampling.py (Qin, 2020). For snowball sampling, the only tunable parameter is . The considered test range for was all positive integers in These histograms are given in Figures 4-13. Each histogram visually approximates the center and spread of degrees of sampled nodes. Across five algorithms and networks, there are 5 × 2 = 10 histograms. Note that each histogram uses data based on nodes accumulated over 10 trials on the same network.
In Figures 14-15, 2-sample quantile-quantile (QQ) plots are shown for each pair of network sampling algorithms that contain CQWS. These plots compare the skeweness of CQWS with every other algorithm and highlights whether CQWS has an advantage or disadvantage in sampling nodes of higher degree relative to another algorithm. Note that both x-axis and y-axis use degree rather than quantile of each degree distribution as units.

Discussion
CQWS achieved the highest degree sum in 1000-node sample averaged over = 10 trials compared to all other sampling algorithms for 2 (Table 3). Due to its trainable parameters relevant to node selection, a narrow window ( 1 = 0.07, 2 = 0.29) of highest degree neighbors that CQWS visits each iteration is ideal for sampling networks that have dense connections (high degree density). However CQWS performed more poorly against other algorithms when sampling the sparse 1 network (Table 2) relative to the dense 2 network (Table 3). For 1 , CQWS performed worse than CNARW by a larger margin than the amount of improvement in degree sum over any of the other three algorithms in Table 2. While for 2 , CQWS outperformed all algorithms in degree sum and held the largest margin of improvement against its runner-up, Random Walk, compared to any other algorithm and its corresponding runner-up in Table 3. This performance disparity is further evidenced by comparing Figures 14   and 15, based on a repeat of the same sampling trials for 1 and 2 shown in Tables 2 and 3. As Figure 14 shows, CQWS only outperformed one algorithm (Snowball Sampling) on 1 . When evaluated on the 2 network in Figure 15, CQWS clearly outperformed all other algorithms except CNARW. A QQ plot displays a right-skewed distribution if points start above the 45° line, close in towards the line, and veer back up along the positive x-axis. Right skewness conveys that the algorithm on the y-axis obtained a lower mean degree (and other measures of center of a distribution) across the 10 sampling trials than CQWS. Specifically, this phenomenon occurred when comparing CQWS against CSES in Figure 14 and against each algorithm besides CNARW in Figure 15.
Comparing CQWS against itself across both 1 and 2 also affirmed CQWS's suitability for dense networks relative to sparser networks. The degree histogram of CQWS for 2 in Figure 5  showcases a center of mass leaning more to the right (i.e. towards a higher degree) than the degree histogram of CQWS for 1 in Figure 4.
For distance variance, CQWS achieved better performance than half of the other algorithms when sampling 1 , evidenced in Table 1. However, CQWS performed the worst when sampling 2 as shown in Table 2. In a dense network, there can be high-degree neighbors of visited nodes that are closer to the start node and have not been discovered earlier. By targeting high-degree nodes, there would be some backtracking during sampling because high-degree nodes become more closely packed. This indicates a trade off between degree sum and distance variance.

Conclusion
Comparing the degree sum of several exploration-based network sampling algorithms against the proposed CQWS yielded deep insight into how both criteria and the connectivity of a network affects the sampling behavior in a network. This paper not only compared the performance of four existing algorithms against a newly proposed one, but the results also suggest how algorithms applying strategic criteria such as CQWS and CNARW outperformed algorithms using purely probabilistic rules to sample nodes. Although snowball sampling employs a tunable parameter, the algorithm still performed poorly because it is not deterministic (i.e., sampling the same network twice yields different results). Despite also being nondeterministic, CNARW employs an intelligently designed rule for choosing nodes to visit and thus performed better than the random walk and snowball sampling. Finally, CQWS has the advantage of incorporating the most tunable parameters and being a deterministic algorithm.
For future work, the most viable improvements on the algorithm would be using counting sort algorithm to order neighboring nodes by degree. This will improve the worst-case time complexity from ( ) to ( ). Even this improved time complexity for CQWS does not exceed the worst-case time complexity of some other algorithms (random walk and snowball sampling). However, the effective performance of CQWS on targeting high-degree nodes can be exploited as a second step in a combination of sampling algorithms. In the first step, a computationally cheaper algorithm can quickly generate a preliminary sample on which CQWS uses for parameter tuning. The tuned CQWS model can then performantly generate a larger second sample to identify much more high-degree nodes in the locality of a node of interest.
With its focus on collecting high-degree neighbors, CQWS is suited for tasks such as recommending social media connections, identifying local communities of resources online, and prioritizing logistical tasks drawn from a dependency graph.