This paper researches new unique characteristics of networks - a network relaxation time and an individual node relaxation time, which characterize the stability of a complex network and, accordingly, each node separately to external perturbations. While researching of the complex networks, it is assumed that relaxation time is the number of iterative steps of the corresponding algorithm required to achieve the initial equilibrium numerical values of a certain characteristic after some external perturbation. In other words, the network relaxation time for each node characterize the resistance of a complex network and the individual node relaxation time characterize the resistance of each node to external perturbations, accordingly. In this work, to compute the relaxation time, the decelerated iterative HITS algorithm is used. It is shown, that these characteristics are unique numerical characteristic of network nodes, and they can be used to find the centroids of clusters and combine nodes into groups according to these characteristics - for complex networks clustering. The approbation of the presented characteristics of the relaxation time and the individual relaxation time was carried out on the example of clustering of random networks with clearly expressed clusters. In particular, a randomly generated matrix with dimension 30×30 and 3 clusters and a matrix with dimension 100×100 and 4 clusters were researched.
Complex networks are widespread in nature and technology. For example, networks such as the World
Wide Web, peer-to-peer networks [
Despite the fact that various networks, such as electrical, transport, and information networks, fall
within the scope of the consideration of the theory of complex networks, the greatest contribution to
the development of this theory is made by research of social networks [
An analysis of complex networks that includes the study of statistical and dynamical structural
properties changes that characterise their behaviour, as well as the prediction of the evolution of such
networks, are important directions [
Division of a set of network nodes (objects) into subsets (clusters), within which these objects are
strongly connected, and the connection between individual clusters is relatively small, i.e. partitioning
into clusters and, for example, detecting communities in social networks [
There are many methods of clustering graphs of complex networks [
In this work, we propose to use a new characteristic for clustering complex networks – the relaxation
time [
is some estimate of the relationship between the elements with indices and , which
are included in the cluster .
ways, for example, as the shortest path between nodes and [
can take non-negative values. This estimate can be calculated in various 2. The connectivity between any separate different clusters, for example, and should be minimal, that is (1) (2) (3) (4) Often, in the general case, the sums for all indices are estimated ( is a number of clusters): 2
, By association, in our case, the first factor in the formula for determining the weight corresponds to the first requirement, if it is of great importance, then it is connected by strong ties with a certain bonds are concentrated within their own group (cluster) – this corresponds to requirement 2. number of nodes (including from its own group). If the parameter is of great importance, then the
We can assume that the individual nodes with the highest discriminant weight (the number chosen in advance) will constitute the centroids for clustering, or the basis for formation of clusters that will form the basis of the clusters.
There are numerous clustering algorithms such as K-means [
By definition, modularity is equal to the proportion of the total number of edges that fall into a given
cluster minus the predicted numbers of edges that would fall into the same groups if they were randomly
distributed. The value of modularity lies in the interval [
The modularity is defined as the sum of all pairs where is Kronecker delta (shows whether nodes and are in the same cluster).
The matrix formulation of modularity is as follows. By definition, if the node belongs to the cluster then is equal to 1and else it is equal to 0. Then 1 2 ,
,
2 2
, , ,
, 1 2 , 1 2 , (5) (6)
(7) (4). where is a matrix, having elements
, and is the so-called modularity matrix, which has elements
The modularity of a network without clusters is equal 0 cause the sum of all columns and rows of the matrix that corresponds modularity is equal to 0. 3. Physical meaning of relaxation time In physics, relaxation is understood as the process of establishing thermodynamic (including stochastic) (temperature, charge density, etc.) has the value that go to equilibrium is given by the kinetic equation і | |/
≪ 1, then in the first approximation → lim , 0
0 charge distribution is resolved, i.e., the equilibrium is reached faster. i.e., the higher conductivity and the lower relative permittivity , the faster the heterogeneity of the The concept of relaxation is used in the methods for approximate solution of systems of linear equations, in iterative methods, for example, in methods of coordinate relaxation, block and group relaxation, etc. function
These examples can be described in the following terms. Let us consider a system of equations ⃗ 0, the solution of which is the function . To find solutions, some initial approximation of the is chosen and such an iterative procedure is found. In explicit form it is represented as or in implicit form as that is, there is such an operator that (19) The solution of this equation is
where 0
is an initial perturbation, and is a relaxation time. equation and Ohm's law⃗
⃗ are can be written as where ⃗ is an electric field strength, ⃗ is a charge density.
In the simplest case of a homogeneous environment the next equation immediately follows where the relaxation time is
So, for example, for an environment with conductivity and the relative permittivity , Maxwell's ⃗ 4, the only way. state of the system is given by equations (11-12)
Here we assume an approach and terminology that allows us to consider the described methods in Let us consider a system described by a set of parameters (numbers, functions) . The equilibrium is a solution for which equilibrium by defining some set
defines the equilibrium state of the system. Let's perturbing the system out of
. By choosing some iterative scheme (15), we get the sequence where is considered as the discrete time. if
In the usual case, for a descending sequence| |, |
|, … let’s define a value △, such that △ convergence (usually △=10-4). that value , which determines (20) will be considered (called) as the relaxation time .
So, in the case of researching complex networks, the relaxation time is the number of iterative steps of the corresponding algorithm, which are necessary to reach the initial equilibrium numerical values of a certain characteristic after its perturbation with some predetermined accuracy △ – the condition of
When the recovery of the whole network is researched, the number of iteration steps required for the value of each node to recover (the whole network is recovered) is called the relaxation time of the network after the perturbation of a certain m-th node or (k = 1,..,N, where N is a number of nodes in network). And the number of iterations which are required to recover the particular node whose numerical value was perturbated, will be called the individual relaxation time indicator of the node
(or simply the node after its perturbation.
). That is, the first characteristic characterizes the node in terms of the stability
of the whole network after an external perturbation, the last one characterizes the individual stability of
For example, let's consider some complex network (a directed graph), for which PageRank [
, he gets bored with this wandering, or the page does not have links to other pages, he goes to a random web page again – not by a link, but by manually typing in some URL. It is assumed that the probability that a user wandering the network will go to a certain web page is its rank. Obviously, a node's PageRank is higher the more other nodes link to it, and the more popular those nodes are. its URL explicitly.
Let's assume, there are n nodes , , . . ,
that refer to some node (web page ), and the total number of links from a node to other nodes. Some fixed value is defined as the probability that the user, viewing any web page from the set , will go to the node by a link, and not by typing is that the user will be at this node at some random moment in time: 1
Within the framework of the model, the probability of this user continuing to surf the web from web pages without using links, by manually entering an address (URL) from a random page will be (alternative to following links). The PageRank index for a node is considered as the probability According to this formula, the node rank is calculated by a simple iterative algorithm. In a complex network of nodes, the value of each node , 1,2, … , determines the equilibrium state of this network. After selecting the value of value the number of steps for which 0 , the iterative procedure for finding
for each node that deviates from the is used. The relaxation time of node is (21) (22)
Let introduce the relaxation time of the k-th node in the complex system – . At the initial stage, a set of values of nodes
( ⃑ is a vector form) define as the equilibrium state. This state is determined in accordance with the certain rule, for example, – the HITS or PageRank iterative algorithm, or any rewritten in iterative form:
Calculation of ⃑ in accordance with the selected rule (the iterative algorithm) can always be ⃑ 1 ⃑ , 0,1, … where the numbers of nodes correspond to the vector elements numbers of ⃑; is the operator of one the iterative HITS or PageRank algorithms that are considered in this work; ⃑0 is the initial values of
Note that there are different variants of setting initial values (deviations) for nodes. They can be the same, they can alternately set the deviations of individual nodes, leaving others at equilibrium values, etc. to the formulas:
In this work, as a characteristic whose numerical value is perturbated, a characteristic corresponding
to the iterative HITS (Hyperlink Induced Topic Search) rank algorithm was used. This algorithm was
proposed and developed in 1998 by J. Kleinberg [
are calculated according ∑→ ℎ , ℎ ∑→
, ⃑ . ⃑0 → ⃑ , 0,1, …
⃑0 0
⃑ 0 ⃑ ⃑ , other. nodes. and, respectively (23) (24) (25) (26) (27) (28) (29) (30)
is considered as the solution – ⃑ (these values are equilibrium).
Next, we propose to make some deviation of the score (called perturbation) of the m-th node, as it is shown in the next example: symbol. where defines the deviation (perturbation) score of the m-th vector element; is the Kronecker
The described above means vector forms of the deviation from the equilibrium state one of the leads a non-equilibrium state of the system. elements of the vector ⃑. The perturbation of vector ⃑ due to the perturbation of one of its elements According to the equation (24), for n=0 it can be rewritten: 0 ∑ 0 , taking into account (27) it looks as follows: where the vector ∑
can be defined as ⎛ ⎜ ⎜
⎝ : : 0 1 ∑ ∑
, , 0 0 : ⎞ ⎛ : ⎞ ⎟ ⎜ ⎟ ⎜ ⎟ ⎟ ⎠ ⎝ 0 ⎠ ⎛ ⎜ ⎝ : : ⎜ : ⎟ ⎟ .
⎞ ⎠ after increasing a number of iterations n in accordance to (25).
Taking into account the initial condition 1 come back to the initial equilibrium state ⃑ decrease and convergence to the value μ. , is the k-th node relaxation time after the perturbation of the m-th node, when the Figure 2: Shema of values convergence the of the k‐th node
following condition is satisfied
In the other words, the maximum value of
node is the network relaxation time [
. for ∀ node. 5. Deceleration of algorithm after the perturbation of the m-th
And respectively, the relaxation time of perturbed node called the individual relaxation time of this When calculating the relaxation time for many small networks, a problem arises, which is that the relaxation time (a discrete number of algorithm steps) can be very small, that is, the effect of "small distributive force" occurs. To solve this problem, it is proposed to apply an artificial deceleration of the iterative algorithm. That is, the so-called decelerated iterative algorithms for HITS and PageRank can be used to calculate the relaxation time. Cause the number of connections between the nodes is large, the process of iterative recalculation of the values of the nodes after perturbation of some node and achieving their initial values is fast. It means that we need to make only a few iterative steps to achieve the initial equilibrium state of nodes after perturbation. In other words, a network relaxation is fast. In order to decelerate the relaxation time, we propose to decelerate the HITS or PageRank algorithm, respectively. After the deceleration, the process of convergence to the equilibrium initial values of nodes after their perturbation will be slowed. So, the corresponding decelerated HITS or PageRank algorithm is applied
→. . . . → , , , where 0 1 is a deceleration factor, is the HITS or PageRank algorithm operator. (31) (32) (33) (34) 6. Examples of network analysis characteristic ℎ chosen individually.
Research of complex networks shows that the values of the network characteristics of nodes after
external perturbation and the next recalculation of these characteristics, recover their initial equilibrium
values during some individual time for each node. Comparing the relaxation time with the network
characteristic, the value of which was perturbated, a vague dependence exists, which shows that the
relaxation time is a unique and incomparable numerical characteristic of network nodes [
Within this work, the individual relaxation time is researched, i.e., the relaxation time of the node, which was deviated from the equilibrium state. In this case, we will further use the notation omitting the upper symbol in
.
Also in the work, the general relaxation time of the network for the -th node is researched – the highest value of among ∀
when the -th node was disturbed.
The approbation of the presented characteristics of the relaxation time and the individual relaxation time was carried out on the example of clustering of random networks with clearly expressed clusters. In particular, a randomly generated matrix with dimension 30×30 and 3 clusters and a matrix with dimension 100×100 and 4 clusters were researched.
For each network described by the corresponding matrix, after perturbing the value of the network using decelerated HITS algorithm, the network relaxation time and the individual node relaxation time were calculated. For each network, the deceleration factor of the HITS algorithm and the convergence condition of the numerical values ℎ and to the preperturbed values were
Also, in order to avoid large numerical values that sometimes arise after the using of decelerated algorithms, all the resulting values of the relaxation time indicators were normalized in the interval according to the modularity class (figures 3(a) and 4(a)) and by the network relaxation time and the individual node relaxation time (for the presented examples, the normalized numerical values of these characteristics coincide and are presented in the form of node labels – Figures 3(b) and 4(b)).
The relaxation time of the network, which presented in Figure 1, was obtained as a result of deceleration the HITS algorithm with a deceleration factor 0.9 10 . For the network presented in figure 2 – 0.9 та 10 .
and convergence condition (a) (b)
This paper researches the proposed network node characteristics – the network relaxation time and the individual node relaxation time. The approbation of the presented characteristics of the relaxation time and the individual relaxation time was carried out on the example of clustering of random networks with clearly expressed clusters. It is shown, that these characteristics are unique numerical characteristic of network nodes, and they can be used to find the centroids of clusters and combine nodes into groups according to these characteristics, in other words, it can be used for complex networks clustering.
The proposed and researched in this work numerical network and node characteristics can be used during research and analysis of the network structure, making it possible to identify the most important structural elements. Also, results of the research can be used when building personal search interfaces for users of information and search systems. In turn, it will simplify the process of finding the necessary information.
The given algorithm, like the well-known LSA algorithm, is a cluster analysis algorithm that uses a matrix representation of data. The complexity of the algorithm is determined by the complexity of the PageRank, HITS or any other iterative algorithm, which is used to recalculate node weights.
The novelty of the algorithm is defined by the approach for calculating the weight of nodes (the values of relaxation time of network or relaxation time of nodes), the most significant of which can be used as centres for determining clusters (centroids). If it is necessary to improve the quality of the proposed approach, certain centroids can be passed as input to other well-known algorithms such as Kmeans. 8. References