=Paper=
{{Paper
|id=Vol-1638/Paper100
|storemode=property
|title=Visualization and cluster analysis of social networks
|pdfUrl=https://ceur-ws.org/Vol-1638/Paper100.pdf
|volume=Vol-1638
|authors=Maximilian I. Khotilin,Alexander V. Blagov
}}
==Visualization and cluster analysis of social networks ==
https://ceur-ws.org/Vol-1638/Paper100.pdf
Data Science
VISUALIZATION AND CLUSTER ANALYSIS OF
SOCIAL NETWORKS
M.I. Khotilin, A.V. Blagov
Samara National Research University, Samara, Russia
Abstract. The article is devoted to the analysis of social networks, which are
presented by graphs. The paper presents approaches to the modeling of distribu-
tions of social networks as well as the algorithms used for finding communities,
as well as accounts that have the greater impact on the community.
Keywords: big data, graphs, data visualization, data analysis, clustering, modu-
larity, SCAN.
Citation: Khotilin MI, Blagov AV. Visualization and Cluster Analysis of So-
cial Networks. CEUR Workshop Proceedings, 2016; 1638: 843-850. DOI:
10.18287/1613-0073-2016-1638-843-850
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 signifi-
cance 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 polit-
ical, 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.
1 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,
Information Technology and Nanotechnology (ITNT-2016) 843
Data Science Khotilin MI, Blagov AV…
are user accounts, and edges - the connections between them. For example, a subscrip-
tion in the network such as Twitter, and the attitude of the "friendship" in social net-
works like The Facebook (figure 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 d x i , x j d ij between vertices x i and x j of the
graph G X , 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 x i , x j , defined
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). f k - is the pro-
portion of vertices of G X , U , which has the degree d xi k .
Fig. 2. The distribution of the degrees of vertices
Information Technology and Nanotechnology (ITNT-2016) 844
Data Science Khotilin MI, Blagov AV…
pk Ck ,
zk z
pk e .
k!
Coefficients and are found for a particular segment of the social network.
2 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:
dd
Q
1
Aij i j Ci , C j
2m i , j 2m ,
where A - adjacency matrix, Aij - (i,j) element of matrix A , d i - the degree of i graph
vertex, C i – the label of the vertex (the number of the community, to which the ver-
tex 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
C i , which will maximize the value of modularity.
Fig. 3. The value of the modularity factor in the allocation of different clusters
Information Technology and Nanotechnology (ITNT-2016) 845
Data Science Khotilin MI, Blagov AV…
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 clus-
ters.
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 commu-
nities). 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 prob-
lem 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 (N – a set of nodes
with the number of elements n) [8]. The modularity function will be equal:
𝑘
1 (𝑑(𝑁𝑙 ))2 1 (𝑑(𝑁𝑖 ))2 + (𝑑(𝑁𝑗 ))2
𝑄1 = ∑ (𝑚𝑙 − ) + (𝑚𝑖 + 𝑚𝑗 − ).
𝑚 4𝑚 𝑚 4𝑚
𝑙=1,𝑙≠𝑖,𝑙≠𝑗
Now join the group i and j in one, which is denoted as an𝑁𝑖∪𝑗 = 𝑁𝑖 ∪ 𝑁𝑗 . The modu-
larity function for the new graph will be:
𝑘
1 (𝑑(𝑁𝑙 ))2 1 (𝑑(𝑁𝑖∪𝑗 ))2
𝑄2 = ∑ (𝑚𝑙 − ) + (𝑚𝑖∪𝑗 − ).
𝑚 4𝑚 𝑚 4𝑚
𝑙=1,𝑙≠𝑖,𝑙≠𝑗
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 𝑁𝑗 :
𝑑(𝑁𝑖∪𝑗 ) = 𝑑(𝑁𝑖 ) + 𝑑(𝑁𝑗 ),
Consequently:
(𝑑(𝑁𝑖∪𝑗 ))2 = (𝑑(𝑁𝑖 ))2 + (𝑑(𝑁𝑗 ))2 + 2𝑑(𝑁𝑖 )𝑑(𝑁𝑗 ).
Taking this into account, we obtain:
1 2𝑑(𝑁𝑖 )𝑑(𝑁𝑗 ) 1 𝑑(𝑁𝑖 )𝑑(𝑁𝑗 )
∆𝑄 = 𝑄2 − 𝑄1 = (𝑚𝑖,𝑗 − ) = (𝑚𝑖,𝑗 − ).
𝑚 4𝑚 𝑚 2𝑚
This implies that the greatest growth of modularity occurs by combining groups 𝑁𝑖 and
𝑁𝑗 , for which the value:
Information Technology and Nanotechnology (ITNT-2016) 846
Data Science Khotilin MI, Blagov AV…
𝑑(𝑁𝑖 )𝑑(𝑁𝑗 )
∆(𝑁𝑖 , 𝑁𝑗 ) = 𝑚𝑖,𝑗 −
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 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
- hub – is an isolated vertex which has neighbors belonging to two or more different
clusters;
- outlier – an 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 clus-
ters, 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-
Information Technology and Nanotechnology (ITNT-2016) 847
Data Science Khotilin MI, Blagov AV…
tex is a core, a new cluster is expanded from this vertex. Otherwise, the vertex is la-
beled 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 con-
taining vertex V. new cluster ID is generated which will be assigned to all found verti-
ces.
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 parame-
ters can be carried out using a machine learning system, using a certain network seg-
ments.
4 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;
Information Technology and Nanotechnology (ITNT-2016) 848
Data Science Khotilin MI, Blagov AV…
- 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.
Fig. 6. The graph of the community
This division into clusters can be seen in the figure below:
Fig. 7. The division of the graph into clusters
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.
Conclusion
Presentation of social networks in the form of a graph and its further analysis, includ-
ing 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 exam-
ple, users, affecting several separate communities (in the graph representation - such
Information Technology and Nanotechnology (ITNT-2016) 849
Data Science Khotilin MI, Blagov AV…
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.
References
1. Tan W, Blake MW, Saleh I, Dustdar S. Social-network-sourced big data analytics. IEEE
Internet Computing, 2013; 5: 62-69.
2. Semertzidis K, Pitoura E, Tsaparas P. How people describe themselves on Twitter. Proceed-
ings of the ACM SIGMOD Workshop on Databases and Social Networks, 2013; 25-30.
3. Blagov A, Rytcarev I, Strelkov K, Khotilin M. Big Data Instruments for Social Media
Analysis. Proceedings of the 5th International Workshop on Computer Science and Engi-
neering, 2015; 179-184.
4. Protcenko VI, Kazanskiy NL, Serafimovich PG. Real-time analysis of parameters of mul-
tiple object detection systems. Computer Optics, 2015; 39(4): 582-591 [In Russian]. DOI:
10.18287/0134-2452-2015-39-4-582-591.
5. Ivanov PD, Lopukhovsky AG. Big Data technologies and different methods of presenting
large data. Science and innovations, 2014; 9: 1-10 [In Russian].
6. Gastner M, Michael T, Newman ME. Optimal design of spatial distribution networks.
Physical Review, 2006; 74: 016117-016126.
7. Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical
Review 2004; 69: 026113-026115.
8. Xu X. Scan: a structural clustering algorithm for networks. Proceedings of the 13th ACM
SIGKDD international conference on Knowledge discovery and data mining, 2007; 824-
833.
9. Newman ME. Fast algorithm for detecting community structure in networks. Physical Re-
view, 2004; 69(6): 066133-066135.
Information Technology and Nanotechnology (ITNT-2016) 850