Luciano Da Fontoura Costa
email: luciano@ifsc.usp.br

On the Self-Coincidence Structure of Networks

The characterization of the topological properties of complex networks remains a challenging subject, as it is difficult to define sets of measurements capable of comprehensive characterization of their structure. In the present work, we approach this important and interesting issue from the perspective of the similarity between the nodes of network, while considering several local and global respective topological node properties. Capable of implementing a particularly selective and robust quantification of the similarity between two mathematical structures, the coincidence similarity is adopted in this work for that finality. Given a network, and having each of its nodes described in terms of a set of topological features, the coincidence methodology can then be applied in order to reveal a respective similarity network, which is here called the self-similarity structure of the original network. Several interesting results are obtained by applying this method to model-theoretic as well as real-world networks, including the identification of an opposite relationship between topological and coincidence links in some of the analyzed cases as well, small average node similarity tending to result at hubs and nodes at the core of communities, the understanding of the node(s) with maximum average node similarity as hubs of similarities, as well as the finding that the topological links do not tend to be related to the respective coincidence similarity between the involved nodes.

Introduction

Thanks to the ability of graphs and networks to represent virtually any discrete structure and system, the area of network science established itself as a dynamic and important area along a relatively short period of time (e.g. [START_REF] Barabási | Network Sience[END_REF][START_REF] Newman | Networks: An introduction[END_REF][START_REF] Da | Characterization of complex networks: A survey of measurements[END_REF][START_REF] Da | Analyzing and modeling real-world phenomena with complex networks: a survey of applications[END_REF]).

Though a great deal of initiatives have addressed the characterization of the topological properties of complex networks (e.g. [START_REF] Barabási | Network Sience[END_REF][START_REF] Newman | Networks: An introduction[END_REF][START_REF] Da | Characterization of complex networks: A survey of measurements[END_REF]), there is still no definitive answer regarding sets of these measurements capable of providing particularly comprehensive representations of the network topology, eventually to the level of establishing a fully invertible mapping between the original network and its representation by a set of features. Thus, there is still motivation for new approaches to the characterization of the topological properties of complex networks.

In the present work, we resource to the coincidence similarity index [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF][START_REF] Da | Coincidence complex networks[END_REF] for that finality. Corresponding to the product between the real-valued Jaccard [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF] and the interiority (or overlap, e.g. [START_REF] Vijaymeena | A survey on similarity measures in text mining[END_REF]) indices, the coincidence similarity has been found to allow a particularly selective, sensitive and accurate quantification of the similarity between pairs of mathematical structures including vectors, matrices, functions and fields (e.g. [START_REF] Da | On similarity[END_REF][START_REF] Da | Coincidence complex networks[END_REF][START_REF] Da | Multiset neurons[END_REF]), therefore paving the way to several successful applications to a diversity of fields (e.g. [START_REF] Da | On similarity[END_REF][START_REF] Da | Coincidence complex networks[END_REF][START_REF] Reis | Enzyme similarity networks[END_REF]).

Here, we address the promising perspective of quantifying graphs and networks in terms of the respective distribution of the similarity between several topological properties of the involved nodes and/or subgraphs while simultaneously considering several topological measurements.

The derivation of coincidence networks from original topological networks was brief and preliminary addressed in [START_REF] Da | Coincidence complex networks[END_REF], considering topological measurements taken for each of the nodes in the original network as features to be translated, by using the coincidence methodology suggested in that same work [START_REF] Da | Coincidence complex networks[END_REF], into a respective coincidence network whose interconnections not necessarily correspond to the original links. In this work, we address this interesting possibility in a more systematic and comprehensive manner, taking into account additional topological measurements as well several model-theoretical and real-world networks to be analyzed from the perspective of the distribution of respective similarities.

More specifically, the suggested quantification of the network topological properties in terms of pair-wise similarity values suggested involves the following two-steps: (i) first, the similarity quantification is performed between all possible pairs of nodes in a network, including a node with itself; and (ii) the overall similarity of the network is then gauged in terms of the average and standard deviation of the values obtained in (i).

In addition, the step (i) above immediately yields a respective coincidence network, which can be respectively visualized and studied in several manners. In the present work, emphasis is given to comparing this resulting links in the obtained coincidence network with the topological links in the original network. In this way, it becomes possible, among other possibilities, to investigate if higher coincidence values are eventually associated to the presence of an actual respective topological link in the original network.

Thus, after presenting the proposed method for quantifying the complexity of a network at its successive topological scales, the present work applies this approach to three theoretical models, namely Erdős -Rényi, Barabási-Albert, and Watts-Strogatz, as well as to two real-world data. Several noticeable results are reported, including the tendency of hubs and nodes at the center of communities to have small average node similarity, the identification of an opposite relationship between topological and coincidence links, the possibility to understand node(s) with maximum average node similarity as hubs/prototypes of a network, as well as the verification of lack of relationship between topological connectivity and respective coincidence similarity, therefore suggesting that the latter measurements has substantial potential for complementing the characterization of networks.

This work is organized as follows. We start by briefly presenting the involves basic concepts -including multiset concepts and the coincidence similarity, and follows by describing the application of the similarity-based approach to the quantification of model-theoretical as well as some networks derived from real-world data.

Basic Concepts

Three model-theoretical networks (e.g. [START_REF] Barabási | Network Sience[END_REF][START_REF] Newman | Networks: An introduction[END_REF][START_REF] Da | Characterization of complex networks: A survey of measurements[END_REF]) are considered in the present work: Erdős-Rényi -ER, Barabási-Albert -BA, and Watts-Strogatz -WS in its ring configuration. These network types are respectively characterized by statistical uniformity, scale-free node distribution, and small world property combined with geographical adjacency, and geographical regularity. The ER and BA models are characterized by small average shortest path distances, and the WS model can present this property depending on the rewiring probability. The present work focuses on undirected networks.

Regarding the choice of measurements to be employed for characterizing the topological properties of each node, there are basically two main approaches that can be taken: (a) to incorporate as many measurements as necessary to provide a comprehensive representation of the topological properties; and (b) to adopt a set of measurements that are of particular interest respectively to each research and applications. Here, we chose an intermediate possibility, in the sense that we adopt a set of measurements that is reasonably comprehensive and still convey information about topological properties of special interest regarding the distance between nodes, as well as the local interconnectivity around the nodes. More specifically, the following node-related measurements are employed in the present work (e.g. [START_REF] Da | Characterization of complex networks: A survey of measurements[END_REF]):

[1] -Node degree: The node degree, corresponding to the number of connections existing between that node and the remainder of the network, constitutes arguably the most important topological property of a node in a graph or network. Here, we consider its average k a v and standard deviation k s d;

[2] -Clustering coefficient: The clustering coefficient, or transitivity, of a node measures how much the neighbors of that node are interconnected. Here, we take into account its average cc a v and standard deviation cc s d;

[3] -Average and standard deviation of the shortest path lengths: Given a node, it is possible to identify its shortest paths to all other nodes in the network, each with its respective number of links, which is understood as the length of the path. The average sh a v and standard deviation sh s d of this measurement taken respectively to all networks nodes is are adopted here as topological measurements, therefore providing valuable information about the overall proximity between the network nodes;

[4] -Betweeness centrality: This interesting measurement quantifies the participation of a given node respectively to the overall structure of shortest paths in the respective network. We adopt its average bt a v and standard deviation br s d in order to reflect this interesting property of the nodes in the considered networks. Thus, we have a total of five features characterizing each of the network nodes according to a mixture of local and global properties.

It is interesting to observe that the degree and clustering coefficient measurements can be understood as being local, as they reflect the topological properties around the most immediate neighborhood of each node. The other two measurements, namely the average shortest path length and the betweeness centrality can be said to be global because they convey information about the overall topology of the network. Therefore, the set of adopted topological measurements constitute a good balance between local and global measurements.

Similarity indices have been often considered in order to compare sets and other mathematical structure (e.g. [START_REF] Cha | Comprehensive survey on distance/similarity measures between probability density functions[END_REF][START_REF] Akbas | L1 norm based multiplicationfree cosine similiarity measures for big data analysis[END_REF][START_REF] Mirkin | Mathematical Classification and Clustering[END_REF][START_REF] Hamers | Similarity measures in scientometric research: The jaccard index versus salton's cosine formula[END_REF][START_REF] Leydesdorff | On the normalization and visualization of author co-citation data: Salton's cosine versus the jaccard index[END_REF][START_REF] Kavitha | Evaluation of distance measures for feature based image registration using Alexnet[END_REF][START_REF] Brusco | A comparison of 71 binary similarity coefficients: The effect of base rates[END_REF]). The coincidence similarity index was suggested [START_REF] Da | Further generalizations of the Jaccard index[END_REF][START_REF] Da | On similarity[END_REF] as an enhancement of the widely applied Jaccard index (e.g. [START_REF] Jaccard | Distribution de la flore alpine dans le bassin des dranses et dans quelques régions voisines[END_REF][START_REF] Jaccard | Étude comparative de la distribution florale dans une portion des alpes et des jura[END_REF][START_REF] Kavitha | Evaluation of distance measures for feature based image registration using Alexnet[END_REF][START_REF] Samanthula | Secure multiset intersection cardinality and its application to jaccard coefficient[END_REF][START_REF]Jaccard index[END_REF][START_REF] Schubert | A note on the Jaccardized Czekanowski similarity index[END_REF]) with two main motivations in mind: (i) to complement the Jaccard index in order to incorporate information about the relative interiority between the two compared structures; and (ii) to allow consideration of real-valued real values. The coincidence similarity is based on multiset theory (e.g. [START_REF] Hein | Discrete Mathematics[END_REF][START_REF] Knuth | The Art of Computing[END_REF][START_REF] Blizard | Multiset theory[END_REF][START_REF] Blizard | The development of multiset theory[END_REF][START_REF] Mahalakshmi | Properties of multisets[END_REF][START_REF] Singh | Complementation in multiset theory[END_REF]).

Given that all adopted measurements are non-negative, we can limit our attention to the multiset coincidence between two non-negative real vectores x and y, which can be defined as:

C( x, y) = min { x, y} max { x, y} min { x, y} min { x, y} (1)
where v indicates the sum of the elements of vector v. The two terms in the above equation correspond to the Jaccard and interiority indices, respectively. Conveniently, we have that 0 ≤ C( x, y) ≤ 1.

In the present work, the features to be compared by the coincidence similarity are preliminary normalized by dividing each value by the respective average of each type of feature. This normalization is related to normalizing the features to result in densities with unit area, but larger feature values are obtained by using the adopted normalization.

The coincidence methodology to translate datasets where each element is characterized in terms of M features (or measurements) into a respective network [START_REF] Da | Coincidence complex networks[END_REF] involves representing each data element as a node, while the weights of the links between two nodes correspond to the respective pair-wise coincidence values between those two nodes. Therefore, the higher the coincidence value, the stronger the connection in the obtained coincidence network.

3 Average Node Similarity and the Self-Similarity Structure

In the present work, we transform the original network of interest into a dataset of elements, corresponding to the nodes, characterized in terms of respective feature vectors involving the five topological measurements described in Section 2. The coincidence methodology is then applied in order to transform this dataset into a respective coincidence network. The original network has N nodes.

The average similarity of a specific node i can now be defined as corresponding to:

C i = 1 N N k=1 C( v i , v k ) (2)
where v i and v i are the feature vectors describing the topological properties of nodes i and k, respectively.

The self-similarity structure of the original is henceforth understood as the coincidence network derived from the original network as described above. As such, it provides comprehensive information about the degree of similarity, as revealed by the coincidence index, between all pairs of nodes in the network of interest, including between the node and itself. This structure can be characterized by the distribution of the average node similarity of its nodes, as well as by the respective average C and standard deviation σ C .

Interestingly, several interesting questions arise in consequence of the introduction of the above measurements. For instance, given a network or one of its subgraphs, the respective node with the highest average node similarity can be understood as a hub of similarity [START_REF] Da | Supervised and unsupervised pattern recognition and their performance[END_REF], therefore representing a possible prototype for that network. Another interesting point regards if it is possible to have networks specific distributions (e.g. scale free) of average node similarity, also motivating the problem of designing networks with given distributions of this measurement. In a sense, all concepts and methods that have been developed in terms of the node degree and average node degree can be extended or revisited from the perspective of the average node similarity.

Model-Theoretic Networks

Having presented the basic concepts and methods to be employed in the present work, we now proceed to applying them to study model-theoretical networks, more specifically ER, BA and WS. All networks presented in the subsequent figures have been threshold for the sake of improved visualization.

Figure 1(a) shows the original networks (in blue) superimposed on the coincidence networks obtained for the ER example, with N = 50 nodes and uniform interconnection probability p = 0.15. The average node similarity is indicated by the size of the nodes in the presented network. Of particular relevance is the complete lack of relationship between the original and coincidence links. One aspect of particular interest regards possible relationship between the average node similarity and node degree. Figure 2 illustrates the respective scatterplot obtained for the above ER network, which indicates very small joint variation for this type of uniformly random structure.

The considered BA network with m = 2 and N = 50 and respective histogram of average node similarities are depicted in Figure 3, resulting in overall average of 0.4615 and standard deviation 0.2449. Interestingly, the average node similarities resulted much smaller than for the ER, reflecting the more heterogeneous structure of this network respectively to the several considered topological measurements taken as features. It is interesting to observe the small average similarity of the hubs. The considered WS network and its respective histogram of average node similarity is presented in Figure 4. The WS network has N = 50 nodes, connections with two neighbors ate each side of a node, and rewiring probability of p w = 0.02. The resulting overall average node similarity is 0.6463 and standard deviation 0.2175, which is higher than the values obtained for the ER case above. The histogram profile also resulted shifted to the right, as could be expected given that the relatively small rewiring probability has not been enough to substantially change the original topological regularity of this network. It is of particular interest to observe the small average node similarity obtained for the nodes at the extremities of the rewired connections.

(a)

Real-World Networks

In order to complement the study of the application of the average node similarity concept for the characterization of networks, we now consider two real-world structures, namely the Zachary karate club [START_REF] Zachary | An information flow model for conflict and fission in small groups[END_REF][START_REF] Csardi | The igraph software package for complex network research[END_REF] and a network of interconnections between the cortical areas of the macaque, [START_REF] Négyessy | Prediction of the main cortical areas and connections involved in the tactile function of the visual cortex by network analysis[END_REF][START_REF] Csardi | The igraph software package for complex network research[END_REF].

Figure 5 illustrates the Zachary karate club network, which is understood to have two communities, superimposed to the average similarity network (a) and respective histogram of average node similarity. The overall average node similarity was 0.4728 with a standard deviation of 0.2590. Interestingly, this histogram bears similarity with that obtained for the ER case. We can observe that the center of the two communities, which are hubs, resulted with substantially small average node similarity in a similar manner to the hubs in the BA case. Interestingly, the nodes mediating the two communities also resulted with small average node similarity as a consequence of their connections to two distinct modules.

Indeed, as it can also be observed respectively to the BA case, the topological links tend to opposite the coincidence links. This tendency can be readily confirmed by the scatterplot between the nodes degrees and the average node similarity presented in Figure 6.

The macaque network and respective histogram of the average node similarities are depicted in Figure 7, yielding overall average 0.5647 and standard deviation 0.2065. This originally directed network has been symmetrized (b) for the sake of compatibility with the clustering coefficient measurement. An interesting, moderately skewed histogram has been obtained in this case, with median average values, being similar to that obtained for the ER networ.

The joint visualizations of the original and coincidence similarities obtained for the macaque network, which can be seen in Figure 7(a), has a moderately modular structure. Interestingly, relatively fewer coincidence links can be observed at the core of the denser community, while the hubs are again characterized by small average node similarity. In addition, this network is characterized by a remarkable uniformity of average node similarity values, indicating that it is particularly uniform respectively to the adopted features.

Concluding Remarks

The present work has addressed the still challenging issue of topological characterization of the properties of complex networks in terms of the concept of coincidence similarity, which is capable of particularly selective, sensitive and robust performance. After presenting the concepts and methods, they were respectively applied to three model-theoretic networks, as well as to two real-world structures.

Several interesting concepts and results have been presented and discussed, including: (i) the strongly skewed histogram obtained for the BA case; (ii) the fact that hubs have been found to be invariably characterized by small average node similarity; (iii) a strong negative correlation between the node degrees and the average node similarity in the case of the BA and Zachary networks; as well as (iv) the identification, in the case of the macaque network, that nodes more central to the cores of the modules tend to have small average similarity; (v) the verification that the local topological structure of a network (individual links) bears virtually no relationship with the strengths of the respective links in coincidence networks; and (vi) the understanding of the node(s) with the highest average node similarity as a hub of similarity of the network (or any of its subgraphs or modules), therefore constituting a reasonable respective prototype.

The reported concepts, methods, and results corroborate the potential of the average node similarity for characterizing in a comprehensive and effective manner the topology of virtually every type of network, paving the way to a number of interesting future works. For instance, it would be interesting to extend the analysis to directed networks, as well as to understand the average node similarity as an indication of the regularity or uniformity of networks. Then, we have that all concepts and methods developed with basis on the node degree can be revisited and/or complemented from the perspective of the average node similarity. In addition, by calculating the average node similarity for successively larger subgraphs, relationships can be established with the network self-similarity (fractal). The identification of nodes with particularly low average similarity also constitutes a possible way to identify outliers. Another particularly promising prospect regards the extension of the similarity concept for quantifying the relationship and matching between two or more networks, including applications to auto and isomorphism.

Figure 1 (

 1 b) shows the respective histogram (a) of average node similarities (coincidences). Interestingly, the average of the average node similarity resulted equal to 0.5733, which is not far from the middle of the possible excursion of similarity values, which are constrained in the interval [0, 1]. A small standard deviation of 0.1937 has been obtained, corroborating the regularity expected from ER networks.

Figure 1 :

 1 Figure 1: The ER network (a) and respective histogram of the average node similarity (b) considering each of the N = 50 nodes. Each node was characterized by five features: node degree, clustering coefficient, betweenness centrality, as well as the average and standard deviation of the the shortest path lengths. The overall average is 0.5733, with standard deviation 0.1937.

Figure 2 :

 2 Figure 2: The scatterplot between the node degrees and the average node similarities obtained for the above ER network. A Pearson correlation coefficient of 0.1345 has been obtained, indicating lack of joint variation between these two features regarding this type of uniformly random networks.

Figure 3 :

 3 Figure 3: The considered BA and average networks (a) with m = 2 and respective histogram of average node similarity (b), with the size of the nodes reflecting the respective average similarity values.

Figure 4 :

 4 Figure 4: The considered WS network (a) with rewiring probability pw = 0.02 and 2 connections to each side, and its respective histogram of average node similarity (b).

Figure 5 :

 5 Figure 5: The Zachary karate club network (a) and its respective histogram of average similarities established by each of the N = 34 nodes. A particularly heterogeneous distribution can be observed that resembles that obtained for the BA case in Section 4.

Figure 6 :

 6 Figure 6: Scatterplot of the average node similarities in terms of the respective node degrees for the Zachary karate club network confirms an opposite tendency of topological and coincidence links for this network. The Pearson correlation coefficient is -0.86.

Figure 7 :

 7 Figure 7: The macaque network and average similarity networks (a) and respective histogram of the average node similarities obtained for the N = 45 nodes of this network.

Acknowledgments.

Luciano da F. Costa thanks CNPq (grant no. 307085/2018-0) and FAPESP (grant 15/22308-2).

Note:

As all other preprints by the author, this work is possibly being considered by a scientific journal. Respective modification, commercial use, or distribution of any of its parts are not possible. This work can be cited by using the respective ResearchGate identification and/or DOI number. Thanks for reading.