{'fraction_non_alphanumeric': 0.028051636799389944, 'fraction_numerical': 0.009967863173375457, 'mean_word_length': 4.67191844300278, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complex network classification using partially self-avoiding deterministic walks

Complex networks have attracted increasing interest from various fields of science. It has been demonstrated that each complex network model presents specific topological structures which characterize its connectivity and dynamics. Complex network classification rely on the use of representative measurements that model topological structures. Although there are a large number of measurements, most of them are correlated. To overcome this limitation, this paper presents a new measurement for complex network classification based on partially self-avoiding walks. We validate the measurement on a data set composed by 40.000 complex networks of four well-known models. Our results indicate that the proposed measurement improves correct classification of networks compared to the traditional ones.


I. INTRODUCTION
Due to the development of informatics, the acquisition of huge data sets has become possible. The analysis of these huge data sets migrated from few individual components (nodes) to a huge number of components all of them interconnected (links) 1 . It has been noticed that many systems have physically close nodes highly connected and distant nodes are weakly connected. As a consequence, a new type of topological structure emerged [2][3][4] . This new structure interpolates the regular lattice and the random (Erdõs and Rényi) one 5,6 . This change of paradigm has made the junction of the mathematical graph formalism (associated to finite systems) with the statistical physics analysis in a new type of topological structure, which has been named complex network. It has been realized that the complex networks can describe several types of topological structures of our daily lives ranging from informatics systems (computer connections in www or internet pages referencing) to biology (protein structures 7 , metabolic networks) passing through social systems (scientific citation 8 , actors network, disease and rumor propagation, linguistics 9 etc.), and pattern recognition 10? -13 .
To use complex networks formalism in a given system, one must firstly specify which parts of the system form the nodes and how these nodes are interconnected. It has been shown that completely different real systems may share a common topological structure.
Thus, one is concerned in how to differentiate them through topological measurements 11 .
For a robust network classification, representative measures must be extracted. The problem is how to define a set of measures that is the most appropriate for a specific application. Several measures have been proposed such as the average number of connections of a node 10,14 , hierarchical degree 14,15 , clustering coefficient 14 , assortativity etc. Nevertheless, many of these measures are correlated, leading to redundancy 14 . Although optimal results are not guaranteed, the use of statistical methods (such as principal component analysis or linear discriminant analysis) to select and improve the measure set is an alternative to solve redundancy and subjective selection 14 .
Here we propose to consider networks, with each link having a weight (weighted network) and to use of a new way to classify them. We propose to use agents that leave from each node and go to the closest neighbor (the smallest link weight) that has not been visited in the preceding µ time steps. This partially self-avoiding deterministic rule can be modified so that the agent goes to the furthest (the strongest link weight, instead of the closest one) neighbor at each time step. Although the partially self-avoiding walk rules are simple, the agent trajectories are complicated and lead to an effective exploration of the network.
The closest (furthest) neighbor rule produces trajectories that explore locally (globally) the network. In this study, the partially self-avoiding walks have been applied to classify four kinds of networks: Erdõs-Rényi, geographical, small-world and scale-free. This simple procedure allows our method to achieve results in network classification that are better than the traditional ones. We call attention that a similar technique has been successfully employed in the classification of image texture 16 . This paper is organized as follows. In Sec. II, a brief review of the results of partially self-avoiding walks is presented. In Sec. III, we describe the partially self-avoiding walk methods for network classification. Numerical experiments and results are presented in Sec. V. Finally, in Sec. VI, concluding remarks and possible extensions of the method are presented.

II. PARTIALLY SELF-AVOIDING WALK
Random walks in regular or random environment have been extensively studied 17,18 . Nevertheless, deterministic walks in regular 19,20 or random 21 environments also present interesting results. These results can be applied to a whole variety of practical situations such as: image analysis 16,22,23 , pattern recognition 24 , fractal 25 , thesaurus dictionaries 26 , optimization 27 , etc.
For instance, consider a partially self-avoiding deterministic walk, where an agent wishes to visit N points randomly distributed in a map of d dimension. These points can be considered as sites and the agent can move from one to another following the rule of, at each discrete time step, going to the nearest site not visited in the previous µ steps. The agent performs a partially self-avoiding walk, where the self-avoidance is limited to the memory window τ = µ−1. Although the dynamical deterministic rule is simple, the agent trajectory can be very complicated 28,29 .
The agent movements depends strictly on the data set configuration and on the starting site 28,29 . They are entirely performed based on a neighborhood table, so that the distances among the sites are simply a way of ranking their neighbors. This feature leads to an invariance in scale transformations 24 . Starting from given point, the trajectory starts with 3 the agent visiting preferentially new points and ends in a cycle, where the same sequence of p ≥ µ + 1 points are visited (see Fig. 1). The beginning of the trajectory has a transient time t and the ending cycle has a period of p or a p-attractor. Notice that t and/or p are different for different starting points so that a transient time and attractor period joint distribution S (N ) µ,d (t, p) can be computed for the N generated trajectories. One obtains the same trajectories for the same point configuration regardless the scale one is dealing.
The most trivial case to deal with the deterministic agent is to consider µ = 0. The agent remains in the same site and the trajectory has null transient time and an attractor with period p = 1. The transient time cycle period joint distribution is simply given by: 1 , where δ i,j is the Kronecker delta. Despite its triviality, this becomes interesting because it is the simplest situation of a stochastic version of this partially selfavoiding walk [30][31][32] .
where Γ(z) is the gamma function and I d = I 1/4 [1/2, (d + 1)/2] is the normalized incomplete beta function. In the limit d → ∞, one is able to calculate it analytically 34 : When greater values of µ are considered, the cycle distribution is no longer peaked at p min = µ + 1, but presents a whole spectrum of cycles with period p ≥ p min 28,29,34-36 .
Another possible way to deal with these partially self-avoiding deterministic walks is to consider a two dimensional lattice and randomly distribute random weights to the (µ + 1) th nearest neighbors so that a given agent, with memory µ, explore the lattice. This system is depicted in Fig. 1.

III. COMPLEX NETWORK MODELING
Below we describe how this partially self-avoiding walks can be used to classify networks.
We start presenting how to perform these walks on networks. Next we use the transient time cycle period joint distribution to create a vector that characterizes the topology of the

network.
A. Partially Self-avoiding Walks on Networks Since weight equalities may occur and the agent does not know where to go, one creates the set: to represent a set of vertices, so that these vertices are the closest (with respect to the weights) to the given vertex t i and do not belong to the memory set M i . Depending on the 5 chosen movement rule, at each time step, the agent leaves its vertex and go to the nearest one (defined by arg min) or furthest one (switching arg min por arg max in Eq. 3). The trajectory is iterated by Eqs. 3 and 4.
To solve possible equalities in ζ, if ζ has only one element, this is chosen as the following vertex to the agent. Otherwise, the equality is solved by a function φ that returns only a vertex. This function may return a vertex randomly chosen or execute a more sophisticated After a transient time t, the agent is trapped in an attractor with period p. The trajectory can be iterated up to a determined number of steps and it searches for an attractor, or at each time step, determine if an attractor has been reached and finish the trajectory. The attractor detection is defined by considering ϕ(v) as the vertex index v, i.e. ϕ(v 1 ) = 1, ϕ(v 2 ) = 2. If p,it = 0, an attractor with period p and transient time t = it − 1 have been detected. If ζ = ∅, the agent has not found any attractor and p = 0 with t = i. An efficient computational strategy to find attractors can be found in Ref. 16 .

B. Signature Vector
The transient time and cycle period joint distribution S µ,d (t, p) stores a great quantity of information concerning the partially self-avoiding deterministic walk in a given environment.
To effectively use these walks, relevant information must be extracted from S (N ) µ,d (t, p). This relevant information is stored in a signature vector ψ µ,din , where din represents the dynamics adopted, for instance, the agent going to the nearest or furthest vertex.
An important issue raised about the partially self-avoiding deterministic walk concerns the movement rule din adopted by the considered agent. On one hand, agents guided for the shorter distance are appropriate to find attractors in regions with high homogeneity. On Trajectories produced by different rules on a graph have distinct patterns for the same graph, as can be seen in Fig. 2. In this work, only two movement rules were used: din = max, the agent moves to the furthest vertex and din = min, the agent moves to the nearest vertex.
The signature vector ψ µ,din is supposed to characterize the environment where the walks 7 have been performed. To compose the signature vector, an interesting strategy is to built a histogram h µ,din (t + p) 16 from the (t, p)−joint distribution. This histogram represents the number of walks that has a length of (t + p), where t and p are the transient time and period of the attractor, respectively. From the histogram, n descriptors are used to compose the signature vector ψ µ,din , The first descriptor is on position µ + 1, because there is no smaller period.
The (t, p)−joint distribution depends on the value of µ and the movement rule din. To capture information from different sources and scales, a signature vector ϕ consisting of the concatenation of ψ µ,din with multiples µ values and different movement rules din is built: The algorithm for the proposed measurement is presented below. First, walks are per-

IV. ANALYSIS OF THE PROPOSED METHOD
In this section, we present an analysis of the proposed method with regard to the complex network features, such as average degree and number of vertices. In Fig. 3, histograms of walk length for complex network models built using N = 50000 and vertex degree mean k = 5 are presented. For purpose of comparison, each column represents an iteration of the same model and each row represents a complex network model. It is possible to note that the histograms present distinct patterns and therefore, we can conclude that the walks can be used to characterize each complex network model. Table I shows four statistics calculated   8 from the histograms. From this table, it is shown that the mean of the walk lengths on the scale-free model is the longest. It occurs because most vertices have few connection, which makes difficult to identify attractors. On the other hand, the mean of the walk lengths on the geographical networks is the shortest. In geographical networks, the vertices are connected in proportion to spatial distance, which helps to formation of groups of connected vertices and thus the identification of attractors.   small length and decay as the walk length is increased. As an example, the mean, standard deviation, entropy, skewness and kurtosis of the histograms are given in Table II.

V. EXPERIMENTS AND RESULTS
To evaluate partially self-avoiding deterministic walks as a complex network measurement, experiments were performed on a data set composed by 40.000 artificial networks.
The complex network models considered in this data set include: Erdõs-Rényi, small-world, geographical network and scale-free. The data set consists of artificial complex networks built with random weight for the edges, number of vertices ranging from N = 100 to 1000  focus is on modeling, we use a simple classifier rather than a more sophisticated classifier such as support vector machines which have been shown to produce superior results but requires more tuning of parameters.

A. Parameters Evaluation
An evaluation of parameters of the partially self-avoiding deterministic walks is presented in the following. Classification results for different values of µ and movement rule din are presented in Table IV. In most cases, movement rule min achieved better classification results than rule max. The former found attractors in homogeneous and local regions, i. e.
regions where the edge weights are low. Figure 6 shows the Principal Component Analysis (PCA) projection considering two dimensions for both movement rules. As we can see, the potential of the movement rule min to obtain separated clusters is evident from this example. Another important result is that the concatenation of both rules ([min max]) increased the correct classification rate. This is because the strategy keeps local and global information from the complex network, providing a powerful framework to complex network characterization.  Results from Table IV also showed that for both movement rules, the correct classification rate is decreased as the memory is increased, except for µ = 0 which is the trivial case of the deterministic walk. These results lie on the fact that a walk has more difficulty, as the memory increases, in finding an attractor in the image 16 . On the other hand, small values of memory µ perform a better local analysis of the network structure, resulting in an higher correct classification rate. As an illustration, Figure 7 presents the first two PCA discriminant for different values of memory.
Results using signature vectors composed by the concatenation of multiple values of memory are presented in Table V. This strategy diminishes the importance of individual values of µ and allows walks with a higher range of lengths, thus providing more robust characterization. In Figure 8, PCA projection of signature vectors composed by multiple values of µ (0, 1, 2, 3, 4, 5) is shown.

B. Multivariate Analysis of Variance
Here, we determine whether the means of the feature vectors differ significantly among the four classes of complex networks. To answer this question, we apply the multivariate analysis of variance (MANOVA) 38 . The MANOVA takes a set of grouped data composed walks and extract the feature vector as in the previous experiments. Thus, one has a data matrix of 4000 rows (1000 samples for each class) and 60 columns (features). Figure 9 depicts the scatter plot matrix for the first four features. On the bottom panel, the figure shows the box plots for different classes.
Considering the means of the four classes by µ 1 , µ 2 , µ 3 , µ 4 , we perform the MANOVA to test the hypothesis that µ 1 = µ 2 = µ 3 = µ 4 . The test of homogeneity (equality) of variance is performed. Once the variances are equal, the means are tested and the hypothesis of equal means is rejected even at the 1% significance level.
In Figure 10, we generate a dendrogram of the class means after the MANOVA. To obtain the dendrogram, the single linkage method is applied in the matrix of Mahalanobis distances between class means. The ordenate represents the distance in which two classes is connected. In this way, one observes that the random network and the geographical network produce features with the most similar characteristics. Also, the scale-free is the network which produce the most different features from the other three networks. These results is corroborated by the plots of Figure 9.

C. Correlation with Traditional Measures
The network classification obtained with the partially self-avoiding deterministic walks are compared to the traditional methods. The results of these comparisons are shown in

VI. CONCLUSION
Here, we have presented a new method to classify complex network based on self-avoiding deterministic trajectories generated by agents leaving from each site of a given weighted network. The agent movements are given by a rule which may characteristics is to forbid visitation to vertex recently visited, with a memory µ. The trajectories formed by these agents, have a transient time and finish in a cycle with an attractor with a given period.
Form the transient time and attractor period joint distribution, we build a signature vector.
It is with this vector that one classifies the networks types. So that, the agents explore and characterize the complex network topology. Combining walks performed with different values of µ and din, it is possible to include information from different sources and scales and then improve the complex network characterization.
Promising results have been obtained on a data set composed by 40.000 networks of 4 well-known models. Experimental results indicate that the proposed method improves recognition of models compared to the traditional measurements. In addition, our method makes the modeling of complex network feasible and simple, since only the use of this new measurement is enough to obtain satisfactory results of classification.