The article is devoted to the analysis of social networks, which are presented by graphs. The paper presents approaches to the modeling of distributions of social networks as well as the algorithms used for finding communities, as well as accounts that have the greater impact on the community. Representation of the network as a graph Generally, when it talks about objects representing the network, such as social, data visualization concept is closely related to the concept graphs. An important task is to present links in social networks to identify different kinds of dependencies. The graph is a collection of non-empty set of vertices and the set of edges: (- set of vertices, - set of edges). The vertices in a graph, which describes the social network,
In the modern world it is continuously generated a huge amount of data, whether the
data received from the satellite, or sensors in the aircraft, bank transactions, patient
diagnostic data, etc. A special place is occupied by social networks. The
significance of social networks is due to the fact that, on the one hand they are the subject
of socialization of people, and on the other - the most powerful and affordable
political, ideological and economic instrument [
Large amounts of data as well as the relationships (connections) between them must
be present in comfortable and readable form. The data from social networks can be
presented in various forms: a tag cloud, charts, historical flows [
For example, we call the distance d xi , x j d ij between vertices xi and x j of the graph GX , U the length of the shortest path, which connecting these vertices. By chain length the number of its edges is meant. Then, the function d xi , x j , defined portion of vertices of GX , U , which has the degree d xi k . on the set of edges U of graph G , is called graph metric.
The degree of a vertex xi X of graph is the number of edges incident to this vertex d xi .
Empirically, it has been proved that the degree distribution of the various segments of the vast majority of social networks has the following form (figure 2). fk - is the propk Ck ,
zk pk
e z .
k! Coefficients and are found for a particular segment of the social network. 2
To simplify the graph, and also for finding the so-called "communities" in a social network, which is described by graph, the clustering is applied.
There are a number of algorithms and approaches for clustering, one of which is the
modularity [
This functionality was proposed by Newman and Girvan in the process of developing
clustering algorithm of graph vertices [
, where A - adjacency matrix, Aij - (i,j) element of matrix A , d i - the degree of i graph vertex, Ci – the label of the vertex (the number of the community, to which the vertex is belongs), m –the total number of edges in the graph, Ci ,C j - delta-function (one, if Ci C j , zero otherwise).
The task of finding isolation of communities in the graph is reduced to search such Ci , which will maximize the value of modularity. The advantages of modularity may include the following:
modularity simply interpreted. Its value is equal to the difference between the proportion of edges within the community and expected share of links, if the edges were placed randomly;
it is possible to count modularity effectively with small changes in the clusters.
However, there are also some disadvantages:
the functionality is not continuous, and the task of its optimization is discrete.
The approximation schemes are used to find the global optimum. Some of them are
really optimize the functional value, while others choose the value of the modularity
by the best solution found, without warranty of local optimality of solutions;
there is a resolution problem (the functionality does not “see” small
communities). This problem is solved by using the modified functionality, which retains all
the advantages and adds scale parameter [
As modularity describes the quality of separation of the graph in the groups, the
problem of finding the optimal partition of the graph can be approached by solving the
problem of maximizing of modularity. However, using a simple brute force method
to solve this problem is almost impossible, since the number of options for separating
n nodes into k groups grows exponentially with n To solve this problem the “greedy
algorithm” of optimization of modular functions was proposed. This algorithm has its
base in an association of two groups giving the highest increase modularity step by
Let us consider some decomposition of the N nodes into k groups (N – a set of nodes
with the number of elements n) [
( − ∑ =1, ≠ , ≠ ( − ( ( ))2 ( ( ))2 4 4 1 1 ) + ( + − ( ( ))2 + ( ( ))2
). ) + ( ∪ − ( ( ∪ ))2 4
4 ) .
Now join the group i and j in one, which is denoted as an ∪ = ∪ . The modularity function for the new graph will be: ∪ = + + , ( ∪ ) = ( )+ ( ), Consequently: The number of edges within the group ∪ is equal to the sum edges within groups and plus the number of edges between them. In other words: The degree of the united group ∪ is equal to the sum of groups of degrees and : ( ( ∪ ))2 = ( ( ))2 + ( ( ))2 + 2 ( ) ( ).
Taking this into account, we obtain: ∆ = 2 − 1 =
( , − 1
4 2 ( ) ( )) = 1 ( , − ( ) ( )).
2 This implies that the greatest growth of modularity occurs by combining groups and , for which the value: ∆( , ) = , − ( ) ( )
2 is maximal.
It is also seen that the combination of groups, between which there are no edges ( , =0), can not give increasing of the modularity. 3
Apart from finding a community in a social network which is represented by the
graph, the classification of vertices in the graph has a considerable interest.
In the article [
The search begins by first visiting each vertex once to find structure-connected clusters, and then visiting the isolated vertices to identify them as either a hub or an outlier (hub or outlier).
SCAN performs one pass of a network and finds all structure-connected clusters for a given parameter setting. At the beginning all vertices are labeled as unclassified. SCAN classifies each vertex either a member of a cluster or not a member. For each vertex that is not yet classified, SCAN checks whether this vertex is a core. If the vertex is a core, a new cluster is expanded from this vertex. Otherwise, the vertex is labeled as not a member of the cluster.
To find a new cluster, SCAN starts with an arbitrary core V and search for all vertices that are structure reachable from V. This is sufficient to find the complete cluster containing vertex V. new cluster ID is generated which will be assigned to all found vertices.
SCAN begins by inserting all vertices in - neighborhood of vertex V into a queue. For each vertex in the queue it computes all directly reachable vertices and inserts those vertices into the queue which are still unclassified. This is repeated until the queue is empty.
The non-member vertices can be further classified as hubs or outliers If an isolated
vertex has edges to two or more clusters, it is may be classified as a hub. Otherwise, it
is an outlier [
A distinctive feature is the presence of parameters and , which can be set by the user or an expert. At the same time the finding of the optimal values of these parameters can be carried out using a machine learning system, using a certain network segments. 4
In order to test the algorithms mentioned above, the analysis of the community of Samara airsoft group "BPF" if social network “Vkontakte” was produced in order to identify possible communities by breaking into clusters.
The adjacency matrix for the graph (in this case, the state of the friendship between members of the community to each other) is shown in Figure 5 The graph with edges that describe the state of dependency of "friendship" and vertices - members of the group is shown in Figure 6.
For this graph the modularity had been calculated. With the resolution of 0.5 the value of the modularity parameter was 0.021, while the graph has been divided in to five communities. By the way in the communities data includes accounts of people who are: - students together in one university; - graduated from the same school; - those who have been invited by the participant Raguzin; - those who have been invited by the participant Korobov; - those who have been invited by the participant YuriNagulov. This division into clusters can be seen in the figure below: It should be noted quite satisfactory performance of the algorithm for finding the communities on a graph, which represents a relatively small segment of the real social network.
Presentation of social networks in the form of a graph and its further analysis, including clustering and finding dependencies, is an urgent task in Big Data. Using the methods described in this article and approaches permits to produce the classification of the social network segments and find the elements of greatest interest, for example, users, affecting several separate communities (in the graph representation - such as the edge of "hub"). When finding the power distribution of the nodes of the graph, which described the social network, it is possible to carry out modeling of social networks with a given distribution.
The algorithms presented in this article are planned for completion and use in the study of social segments of Samara region. The authors have developed the necessary tools to graph visualization of necessary social networks segments and distributed methods of processing of high-dimensional graphs.