The mathematical method of determining the most influential users

Scientists have proposed a new method for determining the most influential users of social networks - it turned out that the number of connections of a particular individual has little effect on his ability to disseminate information. As one of the model examples was a network formed by friendly accounts in LJ. The article of scientists has not been published anywhere yet, however its preprint is available on the site arXiv.org .
As part of the study, the network was studied as a graph whose vertices represent users, and the edges - the connections between them. Traditionally, it is believed that users who have a large number of connections have the greatest influence - that is, vertices from which many edges emanate. For example, in LJ, these are users who have the most friends.

It turned out that this natural assumption is wrong. In the case of distribution of some information, the users who are “strategically correct” have the greatest influence on the speed of this process. For example, scientists lead a vertex in a graph with a large number of outgoing edges, all of whose “friends”, with the possible exception of perhaps one, have no connection with the rest of the graph (a kind of “outcasts” with a single friend). In this case, such a vertex has little impact on the dissemination of information.

To characterize the location of the vertex in the graph, the scientists used the following algorithm. First, all vertices are removed, from which no more than one edge comes. In the remaining graph, all vertices with no more than one edge are also deleted. This is done as long as there is nothing to delete. All remote vertices get index 1. Then the process is repeated for vertices from which no more than two edges emanate. Such vertices get index 2. And so on. It turns out that the larger the index, the more influential the vertex (in the previous example, the vertex with rogue friends had index 1).
')
The dynamics of the dissemination of information in a social network, the researchers studied with a few examples. In addition to the above-mentioned LJ, scientists have built a network of adult film actors (represented by vertices). Edges connected tops corresponding to the actors who played in the same film. The resulting graph had 47,719 vertices and 39,397 links. The average peak index in this network was 46. The average index in LJ is 12.4.

According to scientists, their model allows to study not only the dissemination of information, but also the spread of infections.

copy / past - lenta.ru/news/2010/02/03/blogs