EVS-модели И.Н. Трофимовой \ перевод
В данном разделе приведен сокращенный перевод отдельных разделов статьи И.Н. Трофимовой - www.spkurdyumov.narod.ru/Obrazo.htm#Ob740.
Модель «Социабельность»
Paul Erdos and Alfred Renyi started from a population of isolated nodes, randomly adding links between nodes, creating random pairs. During this addition of more and more links to randomly chosen nodes some pairs started to be connected with other pairs, and at some critical number of added links the whole population of nodes became a big interconnected cluster. Thus, they found a first order phase transition effect in clustering behavior. A similar effect was observed in various physical phenomena and was called percolation.
Our Compatibility model [14] demonstrated a similar effect: with an increase of agent's sociability (number of contacts that a given agent can check/hold per step), there was a critical value (critical sociability), above which a population created huge clusters of interconnected agents, and below which it represented a number of small groups clustered by interests. A first order phase transition was observed as a function of sociability with the critical point Sc=P0,6, where P is the population size. As we said, this Sc was a threshold between having a population organized into a large number of small clusters as opposed to a small number of large clusters (Fig.2). When sociability exceeded a critical value, it not only forced self-organization of a population into a few large clusters, it seemed to prohibit "small groups of common interests", as there were almost no small clusters left.
The Compatibility model contained features reminiscent of spin glass models, considering an ensemble of N cells, each of which possesses a "resource of life" R, and a k-dimensional "vector of traits" v, where each component can equal +/- 1. Each cell forms connections with other cells, and both the maximal number of connections per cell S, termed the `sociability' and the rate of connection attempts a are fixed and identical for all cells. At every time step each cell i attempts a random connections, and its life resource Ri is adjusted according to the "quality" of its current connections. If Ri>0, the cell dies, to be replaced by a new cell having the maximal life resource R and a random vector of traits. The quality of a contact between i-th and j-th cells is evaluated according to the traits of both cells:
where ( , ) denotes the inner product of two vectors, Tij is the duration of the contact between the cells i and j, and s(T) is the "efficiency of the contact" - for small T it linearly increases, and after several time steps saturates at s =1.
The quality varies between sk for aligned trait vectors, to -sk for anti-aligned trait vectors. For cell i having ni connections and connection set {im},the value of the life resource at the next step is
At each time step, a cell i is randomly chosen and a possible contact cell j, which is not a member of the connection set of i is randomly selected. The possible profit of this connection for both i and j is determined by calculating ?(ni,{im}) and ?(ni,{jk}). If the effect is beneficial to both i and j then the connection is formed.
There are several comments that should be made about the role of sociability in such clustering. Our first point is something missed in random graphs theory: the flexibility of the structure of connections in natural systems. In graph theory links, once established, stayed without change. The rigidity of the links in random graph theory started partially to ease after the introduction of the so-called "small-world" architecture of networks. Thirty years ago Granovetter proposed a concept of weak and strong links, and a clustering coefficient as a ratio between actually established and possible links [Grannovetter, 1973]. This meant that the links, once established, also stayed, but with various weights of importance, and it was implemented in network modeling. In contrast, in our EVS models links were far from being constant. In our EVS, the agents dropped the links for various reasons, simulating "traveling interactions" of particles or bodies in a real world. Even after the phase transition, i.e. after a population demonstrated existence of a structure, relationships between elements in these large, "totalitarian", clusters of interconnected agents were generally dynamic, altering in time while still preserving the global functionality of the structure.
Second, it seems that the value of maximal sociability existing within the population is more important than the distribution of sociability values within a population (i.e. how many agents are with low, average or high sociability within it). The most interesting result in Erdos and Renyi's work was that the critical number of links to add for such a phase transition was equal to the number of nodes, i.e. on average one link per node. It was difficult to judge what exactly was the range of sociability (maximal number of links, which a single node could have), as only the overall number of added links was counted. However Erdos proved that the more a graph is growing, the more even is the distribution of links among the nodes, i.e. nodes are having approximately the same number of links. Does this mean that the critical sociability value (i.e. the number of holding links, that causes a large population to be unified into a large cluster) in the random graph theory would be Sc=1? No, it does not, as Sc is not the average number of links, but rather the maximum number of links that an agent could have in a population.
Investigations of actual clustering behavior in naturally occurring systems showed that a small number of elements that have a sociability dramatically larger than the rest of the population can hold everybody together. "Networkers" called them "hubs". This ability to hold a large number of links makes hubs play the role of structuring elements within a population. The sociability of the Internet's hubs obviously exceeds a critical sociability many times over, resulting in a clustering of the population into large clusters organized around these hubs.
Совместимость дает движение
Предположим, что мы имеем популяцию из P агентов, каждый из которых индивидуален и представим набором (вектором) D характеристик
Табл. П-1. Матрица популяции
|
Параметр 1
|
Параметр 2
|
Параметр k
|
Параметр D
|
Агент 1
|
V11
|
V12
|
V1k
|
V1d
|
Агент 2
|
V21
|
V22
|
V 2k
|
V 2d
|
Агент 3
|
V 31
|
V 32
|
V 3k
|
V 3d
|
|
…
|
…
|
…
|
…
|
Агент J
|
V j1
|
Vj2
|
V jk
|
V jd
|
|
|
|
|
|
Агент P
|
V p1
|
V p2
|
V pk
|
Vpd
|
|
|
|
|
|
Диапазон
|
0 – t1
|
0 – t2
|
0 - tk
|
0 - td
|
Агенты блуждают в окрестности SJ соседей каждый в зоне видимости, случайно выбирая некоторое их количество и проверяет их на совместимость, выбирая наиболее совместимого для контакта.
В EVS модели вычисляется разница совместимостей между двумя агентами и находится для каждого агента минимальная величина сумм разностей совместимостей
P
j = min jk k – 1, …, D: j = 1, …, P (1)
i k-1
Продолжение следует…
|
