This paper studies a genetic algorithm for finding the central vertices in graphs. The algorithm uses a different approach to the solution method presentation and describes a new insight in the crossover process. Studies are conducted to find the optimal parameters of the genetic algorithm such us crossover probability, mutation probability and population size. Based on the results, it can be claimed that with the right parameters, our algorithm shows good running time results with high accuracy of the correct answers.
It is recognized that most real systems and networks exhibit a much higher clustering with comparison to a random null model, which can be explained by a higher probability of the triad formation—a pair of nodes with a mutual neighbor have a greater possibility of having a link between them. To catch the more substantial clustering of real-world networks, the model based on the triadic closure mechanism was introduced by P. Holme and B. J. Kim in 2002. It includes a “triad formation step” in which a newly added node links both to a preferentially chosen node and to its randomly chosen neighbor, therefore forming a triad. In this study, we propose a new model of network evolution in which the triad formation mechanism is essentially changed in comparison to the model of P. Holme and B. J. Kim. In our proposed model, the second node is also chosen preferentially, i.e., the probability of its selection is proportional to its degree with respect to the sum of the degrees of the neighbors of the first selected node. The main goal of this paper is to study the properties of networks generated by this model. Using both analytical and empirical methods, we show that the networks are scale-free with power-law degree distributions, but their exponent is tunable which is distinguishable from the networks generated by the model of P. Holme and B. J. Kim. Moreover, we show that the degree dynamics of individual nodes are described by a power law.
The study of temporal behavior of local characteristics in complex growing networks makes it possible to more accurately understand the processes caused by the development of interconnections and links between parts of the complex system that occur as a result of its growth. The spatial position of an element of the system, determined on the basis of connections with its other elements, is constantly changing as the result of these dynamic processes. In this paper, we examine two non-stationary Markov stochastic processes related to the evolution of Barabási–Albert networks: the first describes the dynamics of the degree of a fixed node in the network, and the second is related to the dynamics of the total degree of its neighbors. We evaluate the temporal behavior of some characteristics of the distributions of these two random variables, which are associated with higher-order moments, including their variation, skewness, and kurtosis. The analysis shows that both distributions have a variation coefficient close to 1, positive skewness, and a kurtosis greater than 3. This means that both distributions have huge standard deviations that are of the same order of magnitude as the expected values. Moreover, they are asymmetric with fat right-hand tails.
1 June 2023 in Chaos: An Interdisciplinary Journal of Nonlinear Science
We examine the dynamics for the average degree of a node’s neighbors in complex networks. It is a Markov stochastic process, and at each moment of time, this quantity takes on its values in accordance with some probability distribution. We are interested in some characteristics of this distribution: its expectation and its variance, as well as its coefficient of variation. First, we look at several real communities to understand how these values change over time in social networks. The empirical analysis of the behavior of these quantities for real networks shows that the coefficient of variation remains at high level as the network grows. This means that the standard deviation and the mean degree of the neighbors are comparable. Then, we examine the evolution of these three quantities over time for networks obtained as simulations of one of the well-known varieties of the Barabási–Albert model, the growth model with nonlinear preferential attachment (NPA) and a fixed number of attached links at each iteration. We analytically show that the coefficient of variation for the average degree of a node’s neighbors tends to zero in such networks (albeit very slowly). Thus, we establish that the behavior of the average degree of neighbors in Barabási–Albert networks differs from its behavior in real networks. In this regard, we propose a model based on the NPA mechanism with the rule of random number of edges added at each iteration in which the dynamics of the average degree of neighbors is comparable to its dynamics in real networks.