VISUALIZATION AND CLUSTER ANALYSIS OF SOCIAL NETWORKS MIKhotilin Samara National Research University
Samara Russia
AVBlagov Samara National Research University
Samara Russia
VISUALIZATION AND CLUSTER ANALYSIS OF SOCIAL NETWORKS E51C669AFF88A50E02AED637FE076EA7 10.18287/1613-0073-2016-1638-843-850 GROBID - A machine learning software for extracting information from scholarly documents big data graphs data visualization data analysis clustering modularity SCAN

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.
Introduction

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 [1]. A number of papers are dedicated to researches of social networks as systems, which contain large volumes of data [2,3,4]. 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 [5], but graphs are more often used for this purpose.

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, are user accounts, and edges -the connections between them. For example, a subscription in the network such as Twitter, and the attitude of the "friendship" in social networks like The Facebook (figure 1).

     Ck k p ,   z e k k z k p   ! .

Coefficients and are found for a particular segment of the social network.

Clustering and communities finding algorithms based on the modularity

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 [8][9]. This functionality was proposed by Newman and Girvan in the process of developing clustering algorithm of graph vertices [7]. Under the modularity means a scalar value from the interval [-1, 1], expressed by the following formula:

  j i j i j i ij C C m d d A , 2 2m 1 Q ,             ,

where A -adjacency matrix, ij A -(i,j) element of matrix A , i d -the degree of i graph vertex, i Cthe label of the vertex (the number of the community, to which the vertex is belongs), m -the total number of edges in the graph,  

j i C C ,  -delta-function (one, if j i C C  , zero otherwise).

The task of finding isolation of communities in the graph is reduced to search such i C , which will maximize the value of modularity.

Fig. 3. The value of the modularity factor in the allocation of different clusters

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 [7]. 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 step. Let us consider some decomposition of the N nodes into k groups (Na set of nodes with the number of elements n) [8]. The modularity function will be equal: ).

𝑄 1 = 1 𝑚 ∑ (

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.

Classification of vertices, finding the most significant, SCAN algorithm

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 [7] the following classification of the vertices was introduced (see figure 4):

-core -is the vertex which contains in ε-neighborhood at least μ vertices -hubis an isolated vertex which has neighbors belonging to two or more different clusters; -outlieran isolated all its neighbors of which either belong to only one cluster or do not belong to any cluster.

Fig. 4. An example of a graph with different types of vertices

To perform such classification a SCAN algorithm is proposed [7]. The principle of its work is described as follows.

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 ver-tex 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 [7].

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.

Experiment and results

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 Fig. 5. The adjacency matrix

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 into 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.

Conclusion

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 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.

Fig. 1 .Fig. 1. A fragment of the graph of social network "VKontakte" One of the main related characteristics that should be considered is the metric. The metric of the graph is based on the notion of distance. For example, we call the distance   ij d j x i x d  , between vertices i x and j x of the
Fig. 2 .Fig. 2. The distribution of the degrees of vertices
Fig. 6 .Fig. 7 .Fig. 6. The graph of the community This division into clusters can be seen in the figure below:
Now join the group i and j in one, which is denoted as an𝑁 𝑖∪𝑗 = 𝑁 𝑖 ∪ 𝑁 𝑗 . The modularity function for the new graph will be: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 𝑁 𝑗 : 𝑑(𝑁 𝑖∪𝑗 ) = 𝑑(𝑁 𝑖 ) + 𝑑(𝑁 𝑗 ),𝑘 𝑙=1,𝑙≠𝑖,𝑙≠𝑗𝑚 𝑙 −(𝑑(𝑁 𝑙 )) 2 4𝑚) +1 𝑚(𝑚 𝑖 + 𝑚 𝑗 −(𝑑(𝑁 𝑖 )) 2 + (𝑑(𝑁 𝑗 )) 2 4𝑚).𝑄 2 =1 𝑚∑ (𝑚 𝑙 − 𝑘 𝑙=1,𝑙≠𝑖,𝑙≠𝑗(𝑑(𝑁 𝑙 )) 2 4𝑚) +1 𝑚(𝑚 𝑖∪𝑗 −(𝑑(𝑁 𝑖∪𝑗 )) 2 4𝑚) .Consequently:(𝑑(𝑁 𝑖∪𝑗 )) 2 = (𝑑(𝑁 𝑖 )) 2 + (𝑑(𝑁 𝑗 )) 2 + 2𝑑(𝑁 𝑖 )𝑑(𝑁 𝑗 ).Taking this into account, we obtain:∆𝑄 = 𝑄 2 − 𝑄 1 =1 𝑚(𝑚 𝑖,𝑗 −2𝑑(𝑁 𝑖 )𝑑(𝑁 𝑗 ) 4𝑚) =1 𝑚(𝑚 𝑖,𝑗 −𝑑(𝑁 𝑖 )𝑑(𝑁 𝑗 ) 2𝑚
Social-network-sourced big data analytics WTan MWBlake ISaleh SDustdar IEEE Internet Computing 5 2013 How people describe themselves on Twitter KSemertzidis EPitoura PTsaparas Proceedings of the ACM SIGMOD Workshop on Databases and Social Networks the ACM SIGMOD Workshop on Databases and Social Networks 2013 Big Data Instruments for Social Media Analysis ABlagov IRytcarev KStrelkov MKhotilin Proceedings of the 5th International Workshop on Computer Science and Engineering the 5th International Workshop on Computer Science and Engineering 2015 Real-time analysis of parameters of multiple object detection systems VIProtcenko NLKazanskiy PGSerafimovich 10.18287/0134-2452-2015-39-4-582-591 Computer Optics 39 4 2015 In Russian Big Data technologies and different methods of presenting large data PDIvanov AGLopukhovsky Science and innovations 9 2014 In Russian Optimal design of spatial distribution networks MGastner TMichael MENewman Physical Review 74 2006 Finding and evaluating community structure in networks MENewman MGirvan Physical Review 69 2004 Scan: a structural clustering algorithm for networks XXu Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining the 13th ACM SIGKDD international conference on Knowledge discovery and data mining 2007 Fast algorithm for detecting community structure in networks MENewman Physical Review 69 6 2004