Printer Friendly

Visualizing social network: a survey.

INTRODUCTION

Social network analysis becomes increasingly more important with growing popularity websites such as facebook, twitter, flickr. A social network is most easily understood as a structure of social actors[23]. The advantage of social network analysis is that unlike, many methods, it mainly focused on interaction (rather than individual behavior).Two types of SNA 1) Ego-centric analysis 2) Socio-centric analysis. Social network analysis used various analytical tools such as UCINET, PAJEK, Gephi, Visone, Vister, Net draw, R. Social network analysis used graph theoretic concepts. Various centrality measures such as degree, closeness, betweenness, eigenvector centrality [1].Eigenvector centrality is an another measure of importance of vertex in a network and several attempts measures to generalize degree, betweenness, closeness centrality for weighted networks [3]. Betweenness centrality is based on random walk and it also used for detecting communities in a social network [4]. Analysis and visualization, has only become more complex network [6]. Sensitivity parameter based on markov importance [6].Social network analysis, has most frequently used measures are betweenness and closeness centrality [9]. Betweenness centrality of vertices Brandes' algorithm take time O(nm) for unweighted graph and O (nm + [n.sup.2] log n) for weighted graph [5]. Randomized algorithm estimating K-path centrality for all nodes [5]. SNA provide both visual and mathematical analysis.

Related Work:

There are different measures of centrality used in network analysis: They are degree centrality, betweenness, closeness and eigenvector centrality.

Degree centrality:

Degree centrality defined as number of links incident upon a node. Degree centrality has defined two names they are in degree and out degree [2]. Time complexity for degree O ([n.sup.3]).

Betweenness centrality:

It is a measure of a vertex within a graph. Vertices that occurs on many shortest paths between other vertices higher betweenness than that [1]. Time complexity for betweenness O ([n.sup.3]).

Closeness centrality:

Closeness is a sophisticated measure of centrality. It is preferred for analysis to mean shortest-path length. Different methods and algorithms to measure closeness, like the random-walk centrality [1].Time complexity for closeness O ([n.sup.3]).

Eigenvector centrality:

It is a measure of importance of a node in a network. It is based on concept of node connections to high-scoring nodes contribute question more than equal connection to low-scoring nodes [1].

System for Social Network Exploration:

Social Network Exploration categories of visualization system 1) System for end user to visualize their personal network and designed for analyzing entire networks. It use only NL. Tool: Vizster.2). Focus on analyst and spend significant time and effort to learn and analysis data.Tool: Pajek It used for analysis large network. Matrix explorer use NL and MAT representation to visualize and explore social network.

Methodology:

A. Markov centrality:

It is a important node in a social network graph and computed as a mean first-passage time in markov chain [6]

M= (I - Z + [EZ.sub.dg]) D (1)

Where I is a Identity matrix, E is a matrix containing all ones, D is a diagonal matrix and Z is called as fundamental matrix, given by:

Z = [(I - A - e [[pi].sup.T]).sup.-1] (2)

Where A is an adjacency matrix and n is a column vector. The importance of node v inverse of average of corresponding column in M: [6].

I (v) = n/[[summation].sub.S[epsilon]V] [m.sup.sv] (3)

B. Sensitivity parameter:

Find the hidden relationship between nodes, sensitivity parameter is an important metrics with degree of another node. The sensitivity analysis methods have described the sensitivity of given function with partial derivative [6].

3Ii

[S.sub.if] = [partial derivative][I.sub.i]/[partial derivative][[[LAMBDA].sub.j] (4)

C. Visualizing Friendship and Enmity:

It is essential for analyzing the social balance of a network, in context the positive link refers Friendship and negative link refers Enmity.

Algorithms:

Various algorithms are defined in centrality measures. They are

D. Brandes ' Algorithm:

Brandes' algorithm [5] computing betweenness centrality it defines the notation of dependency score on any source vertex s on another vertex v.

Recurrence relation is significant to Brandes' algorithm

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The running time for weighted graph is O (nm + [n.sup.2] log n)

And unweighted graph is reduce its running time to O (nm)

E. RA-Brandes Algorithm:

It is estimated for closeness centrality and independent. This algorithm is proposed a Randomized approximate Brandes or short RA-Brandes it is different from brandes' algorithm. The running time for weighted graph is

O (log n/[[epsilon].sup.2] (m + n log n)) and Unweighted graph is O (log n/[[epsilon].sup.2] (m + n)

F. AS-Brandes Algorithm:

Bader et al [5] randomized algorithm estimating the betweenness centrality of all vertices in given graph. It is based on adaptive sampling techniques.

Average score samples: [C.sub.B][v] = n Rs[v]/k[v].

ALGORITHM 1: Betweenness centrality in unweighted graphs[10]
[C.sub.B][v] [left arrow] 0, v [epsilon] V;
For s [epsilon] V do
S [left arrow] emptystack;
P[w] [left arrow]emptylist, w[epsilon]V;
[sigma][t] [left arrow] 0, t [member of] V; [sigma][s] [left arrow] 1;
d[t] [left arrow]1, t [member of] V; d[s] [left arrow] 0;
Q[left arrow]emptyqueue;
enqueue s s[left arrow]Q;
While Q not empty do
dequeue v[left arrow]Q;
push v[left arrow]S;
for each neighbor w of v do
//w found for the first time?
if d[w]<0 then
enqueue w [[right arrow]] Q;
d[w] [left arrow] d [v] + 1;
end
// shortest path to w via v?
if d[w] =d[v]+1 then
[sigma][w][left arrow][sigma][w] + [sigma][v];
Append v [right arrow] P[w];
end
end
end
[partial derivative][v][left arrow]0, v [member of] V;
// S returns vertices in order of non-increasing distance from s
While S not empty do
Pop w[left arrow]S;

for v [member of] P[w]do[delta][v][left arrow]d[v] + [sigma][v]/
      [sigma][w].(1 + [delta][w]);

if w [not equal to] sthen [C.sub.B] [w][left arrow][C.sub.B] [w] +
[delta][w];
end
end


K-Path Centrality

It is random walk betweenness centrality and based on traversal network with random walk. [5]. It traversal at simple path only. Reduce its computational time.

ALGORITHM 2 : Randomized-Approximate k-path
Input: Graph G = (V,E), Array W of edge weights, [alpha] [member of]
       [-1/2,1/2], and integer k

Output: Array [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of
        K-path centrality estimates
begin
   for each v[member of] V do
         count[v][left arrow] 0; Explore[v][left arrow] false;
end

/* S is a stack and n = [absolute value of v] */
T[left arrow]2[k.sup.2][n.sup.1-2[alpha]] 1n n; S[left arrow][theta];
for i[left arrow]1to Tdo
/* Simulate a message traversal from s containing l edges */
s[left arrow]a vertex chosen uniformly at random from V;
1[left arrow]a n integer chosen uniformly at random from [I,k];
Explored [s][left arrow]true; pushstoS; j[left arrow]1;
While (j [less than or equal to] land[there exists](s,u)
  [member of] Es, t. !Explored[u])do

v[left arrow]a vertex chosen randomly from{u|(s,u)[member of] Eand!
  Explored[u]}withprobaility

proportional to 1/W(s,v);
Explored [v][left arrow]true; push v to S;
Count[v][left arrow]count[v]+1;
s[left arrow]v; j[left arrow]j+1;
end
/* reinitialize Explored[v] to false */
While S to nonempty do
  pop--s; Explored[v]--false;
end
end

for each v[left arrow]V do
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
end

A

return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];
end


ALGORITHM 3: Current flow closeness
Input : Electrical network N=(G;c)[7].

Output: Current flow closeness [C.sub.cc]:V [right arrow][IR.sub.>0]
Begin
cCC [left arrow] 0
for v[member of] V do
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
For w [member of] Vdo
Increase [c.sub.CC](v) by Cvv - 2Cwv
Increase cCC(w) by Cvv
for v [member of] Vdo
[c.sub.CC](v) [left arrow] 1/ [c.sub.CC](v)
end


ALGORITHM 4: K-centrality for both betweenness and closeness based on measures
For s [member of] V
Empty predecessors
Dist[] = [infinity]; [sigma] = 0
Dist[] = 0; [sigma] [s] = 1; [N.sup.k.sub.s] = 0
s [right arrow] Queue
while Queue not empty
stack[left arrow]v[left arrow]Queue
for w such that [e.sub.v] [sup.w] [member of] V
if dist[w] = [infinity]
   dist[w] = dist[v]+1
   if dist[w] [less than or equal to]  k
   w [right arrow] queue

   [N.sup.s.sub.k]  + = 1
   If dist[w]=dist[v]+1
   [sigma][w] = [sigma][w] + [sigma][v]
    V [right arrow] predecessors
    While stack not empty
    w [left arrow]stack
    for v [member of] predecessors[ w]

   [delta][v] + = [sigma[v]/[sigma][w]. (1 + [delta][w])

 If w [not equal to] s
    [C.sup.B] [w]+ = [delta][w]
    Distances[s] +=dist [w]
 For se v

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]


G. Figures and Table:
Table I: Time complexity

                   Degree    Closeness    Betweennes

Time complexity     O(m)       O(n3)         O(n3)

Table 2: Different Types Of Social Graph

Types                        Edge

Friendship                   Friendship
Graph                        between users

Interaction                  Visible
Graph                        Interaction,Such
                             as post wall

Latent Graph                 Latent
                             Interaction,Such
                             as browsing
                             profile

                             Subscribes to
                             receive all
                             messages

Following Graph

Table 3: Score based on various centrality measures

                       Degree    Closeness                 Betweennes

A                      6         0.125                     4
B                      9         0.143                     8
C                      3         0.083                     0
D                      2         0.091                     0
E                      3         0.011                     4
F                      1         0.059                     0


[FIGURE 1 OMITTED]

H. Social Network Analysis Software:

Social network analysis software is used for identify, analysis, visualize nodes (eg. Organization or knowledge) and edges (relationship), various input data (includes relational and non relational)[25]. Output data saved in external files. Various tools are
Table 4: Social Network analysis software tools

Product    Function            Input format          Output format

Ucinet     social              Dl, excel             Dl,excel,paj
           network                                   ek,VNA in net
           analysis and                              draw
           visualization

Visone     visual              Many format           Many format
           social network
           and exploration

Gephi      Graph               Ucinet(.dl)           Guess(.gdf)
           exploration         Gephi(.gdf)           Gephi(.gefx)
           and                 Pajek(.gml)
           manipulation
           software

Pajek      Analysis and        .net, .paj,
           visualization of    .dat(UCINET), .ged,
           large networks      .bs, .mac,

R          Social network      R will read any
           analysis within     format data file
           versatile R

Product    Function            platform

Ucinet     social              Windows
           network
           analysis and
           visualization

Visone     visual              Windows,m
           social network      acos
           and exploration

Gephi      Graph               Support all
           exploration         usingjava1.
           and                 6
           manipulation
           software

Pajek      Analysis and        .net, .paj,
           visualization of    .dat(UCINET),
           large networks      .xml(graphML), .bs

R          Social network      R has write
           analysis within     capability data
           versatile R         formats

Product    Function            Description

Ucinet     social              It integrated with
           network             visualization tool
           analysis and        and includes
           visualization       centrality measures
                               and matrix format

Visone     visual              It is a software for
           social network      visualizing social
           and exploration     network

Gephi      Graph               It is a interactive
           exploration         tool and
           and                 Visualization
           manipulation
           software

Pajek      Analysis and        Windows,
           visualization of    mac os
           large networks

R          Social network      Windows, Mac
           analysis within     os, linux
           versatile R

Product    Function

Ucinet     social
           network
           analysis and
           visualization

Visone     visual
           social network
           and exploration

Gephi      Graph
           exploration
           and
           manipulation
           software

Pajek      Analysis and        Calculate centrality
           visualization of    measures and program
           large networks      for graph drawing

R          Social network      R contains several
           analysis within     packages for social
           versatile R         network analysis


I. Approach On Social Network

Various types of approach in social network are used. They are
Table 4: Social Network approach

Approach      Description

Structural    Focus on pattern relations(eg. Structural hole)

Relation      Focus on ties(eg.Weak and Strong ties)

Resource      Focus on resource(Lin's Resource approach 1999)

Cognitive     Focus on perception network

Attributes    Focus on attributes ego(traditional research)


J. Socio-centric analysis:

Socio-centric analysis used for analysis virtual social structure[16]. It is based on relationship among actors.It use different parameters they are

* Strength

* Confirmation

* Multiplexity

K. Ego-Net analysis:

Ego-Net (Egocentric Network study software) for collection and analysis of data. It helps to create the questionnaires and collect data. It analysis (Individual networks).It used various methods they are filtering, alters[16].Tools are available in www.analytictech.com. It reads data in UCINET and ego net analysis. It also reads data in excel(column wise data).Net draw visualize the data in graph format.

Advantage of Ego-Net Analysis

It is possible to extract ego-net from whole network

It is feasible.

Ego-net analysis is compatible.

It allows researchers to move between whole network and individual ego-net analysis.

Disadvantage of Ego-net analysis

Access all its members.

No flexibility during network data collection.

Retrospective answers.

People may not experienced for same things.

Ucinet tool is used for analysis the whole network and personal network. It data format is D1, and excel worksheet.

L. Network Data visualization:

Data visualization defined any techniques used for create images, diagrams or animation to communicate message.

In general,

* Communicate rich messages(communication)

* Unknown facts and relations(discover)

* Better insight

Visualization performed by using i)nodes and connection lines and specific relationship among values. ii)matrices rows and columns. To improve exploration of network Various tools are emerged such as JUNG[26], GUESS[27],yED graph editor. Visualization provide more effective exploration Brande and wagner discuss in visone [11].It provide number layouts and color encoding properties. Heer and Boyd presented for visualizing social network. [12]. A different approach[13] by jai et al approach based on observation scale free network are minimally connected.

Pajek for analysis and visualization of large network. For example pattern searching, search path count weights in acyclic networks, 3-rings and 4-rings weights, cores and generalized cores, network multiplication (analysis of two mode networks),(p; q)- cores, hierarchical clustering with relational constraint. [14].

Various layout are used. They are

* Uniform Layout

* Spectral Layout

* Layered layout

* Radial Layout

Radial Layout

Algorithm for radial graph layout to support centrality visualization. [11].It is similar to hirerarchy structure. Radial layout is focused on the instructor and administrator. It is more flexible.

Two hybrid representations:

Augmenting Matrices

Merging Matrix and Node-Link Diagram

Important parameter of Random Walk

Access time or hitting time

Commute time

Cover time

Application on Random Walk

Ranking Web Pages

HITS on citation network

Clustering using random walk

Ranking Social Networks:

The entire social network is visualized a node-link diagram on left, and a corresponding list of nodes is presented on right. The nodes positioned using a force-directed layout approach, a generic layout algorithm common in many network visualization packages [15]. Social Action allows users to rank nodes in their structural position by choosing a ranking of interest from a drop-down menu. sample choice: [15].

* bary center

* betweenness centrality

* closeness centrality

* cut-points

* degree

* HITs

* power-centrality

Filtering by Rankings:

SocialAction allows users to zoom and filter, users has improves when the number of visualized elements is limited. Users can freely zoom into sections of graph to improve clarity by dragging the right-mouse button. SocialAction also allows users to filter nodes in both the ordered list and network view based on their rankings. Filter based on ranking is important for number of nodes and link crossing will be reduced. [15].

Visualizing Online Social Networks:

Visualization of online social networks is categorized into three types : [13].

* user-centric visualization

* content-centric visualization

* hybrid visualization

1. User-centric visualization:

various characteristics of actors and helps to explore different subjects and relationships of interests[28].For example, to discover individuals. Some measures are

actors.

key actors.

actors with popular interpersonal relationships or active social interactions[30].

2. Content-centric visualization:

Various kinds of contents can be facilitate people analyzing social networks. For example, distribution of user opinions.

user opinions.

Relation among different groups.

3. Hybrid visualization:

Hybrid visualization is to visualize social networks from different aspects. e.g. people and content.

Conclusion:

In this survey Visualizing on social network use various methods. Different types of network used for analysis They are 1) Large network[14] and 2) Individual network. A various randomized algorithm is implemented for analysis. They are betweenness and closeness centrality measures. UCINET tool is used for analysis based on matrix format and to visualize both large and individual network. It has two modes they are 1)one mode attribute and 2) Two mode attribute. Pajek used for visualizing large network. [25]UCINET is best to access. A randomized algorithm is based on K-path centrality and shortest path. An important application for random walk and another scale free social networks. Our General approach is based on Network analysis and centrality metrics. They are used for implementation. socio-centric network analysis is observed relatively high for the correlation of betweenness centrality. Egocentric analysis has different structural characteristics. An SNA measure is flexible in visualization. Users can interactively reduce complexity, find cohesive subgroups, and focus on communities of interest. Different link types, such as temporal evolution. Furthermore the application of methods to time-varying graphs and their integration into an exploration network. On comparing UCINET and Pajek, UCINET gives the best support for Visualizing on the social network. But further generalization can be made only by analyzing other similar datasets.

REFERENCES

[1.] Sanjiv Sharma, Purohit G.N., 2012. A New Centrality Measure for Tracking Online Community in Social Network, I.J. Information Technology and Computer Science, 4: 47-53.

[2.] Daifeng Li, Ying Ding, Xin Shuai, Johan Bollen, Jie Tang, Shanshan Chenc, Jiayi Zhu, Guilherme Rocha, 2011. Adding community and dynamic to topic models, Journal of Informetrics, 6: 237-253.

[3.] Xingqin Qi, Eddie Fuller, Qin Wu, Yezhou Wu, Cun-Quan Zhang, 2012. Laplacian centrality: A new centrality measure for weighted networks, Information Sciences, 194: 240-253.

[4.] Min-Joong Lee, Jungmin Lee, Jaimie Y. Park, 2012. QUBE: a Quick algorithm for Updating BEtweenness centrality, ACM 978-1-4503-1229-5.

[5.] Tharaka Alahakoon, 2011. Rahul Tripathi, Nicolas Kourtellis, Ramanuja Simha, Adriana Iamnitchi, K-Path Centrality: A New Centrality Measure in Social Networks, ACM 978-1-4503-0634-8.

[6.] T arik Crnovrsanin, Carlos D. Correa and Kwan-Liu Ma, 2009. Social Network Discovery based on Sensitivity Analysis, IEEEDOI10.1109/ASONAM.56.

[7.] Kazuya Okamoto, Wei Chen, and Xiang-Yang Li, 2007. Ranking of Closeness Centrality for Large-Scale Social Networks, Illinois Institute of Technology and Microsoft Research Asia.

[8.] Stephen, P., Borgatti, 2006. Identifying sets of key players in a social network, Comput Math Organiz Theor, 12: 21-34.

[9.] Ulrik Brandes and Daniel Fleischer, Centrality Measures Based on Current Flow, STACS 2005, LNCS 3404, pp. 533-544, 2005.@Springer-Verlag Berlin Heidelberg.

[10.] Ulrik Brandes, 2001. A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology, 25(2): 163-177.

[11.] Brandes, U. and D. Wagner, 2004. "Visone-Analysis and Visualization of Social Networks," Proc. Graph Drawing Software, pp: 321-340.

[12.] Heer, J. and D. Boyd, 2005. "Vizster: Visualizing Online Social Networks," Proc. IEEE Symp. Information Visualization, pp: 32-39.

[13.] Jia, Y., J. Hoberock, M. Garland and J. Hart, 2008. "On the Visualization of Social and Other Scale-Free Networks," IEEE Trans. Visualization and Computer Graphics, 14(6): 1285-1292.

[14.] Batagelj, V. and A. Mrvar, 2002. Pajek--Analysis and Visualization of Large Networks, pp: 477.

[15.] Adam Perer, Ben Shneiderman, 2006. Balancing Systematic and Flexible Exploration of Social Networks, IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 12(5): SEPTEMBER/OCTOBER.

[16.] Annalisa Socievole, Salvatore Marano, Exploring User Sociocentric and Egocentric Behaviors in Online and Detected Social Networks, University of CalabriaRende, Italy.

[17.] Danny Holten, 2006. Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data, IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 12(5): SEPTEMBER/OCTOBER.

[18.] Dan Brass, 2014. Introduction to Social Networks: Concepts and Core Ideas, Link center for social network analysis, University of Kentucky.

[19.] Nathalie Henry, Jean-Daniel Fekete, MatLink: Enhanced Matrix Visualization for Analyzing Social Networks, Univ. of Sydney, Australia.

[20.] Long Jin, 2013. Understanding User Behavior in Online Social Networks: A Survey,IEEE Magazine.

[21.] Dirk Kosch utzki and Falk Schreiber, Comparison of Centralities for Biological Networks, Gatersleben, Germany.

[22.] Wasserman, S., K. Faust and M. Granovetter, 1194. Social Network Analysis: Methods and Applications. Cambridge Univ. Press.

[23.] Freeman, L., 2000. "Visualizing Social Networks," J. Social Structure, 1(1).

[24.] Scott, J.P., 2000. Social Network Analysis: A Handbook. SAGE Publications.

[25.] UCINET: Social Network Analysis Software. http://analytictech.com/.

[26.] JUNG: Java Universal Network/Graph Framework. http://jung.sf.net/.

[27.] http://graphexploration.cond.org/, GUESS, 2007. the graph exploration system.

[28.] Stephen P. Borgatti, 2012. Analyzing social network, springer.

[29.] Brandes, U. and T. Erlebach, 2005. Network Analysis: Methodological Foundations. Springer.

[30.] van Ham, F. and M. Wattenberg, 2008. "Centrality Based Visualization of Small World Graphs," Computer Graphics Forum, 27: 3.

(1) K. R. Sri Preethaa and (2) M. Radhika

(1) Assistant Professor, KPR Institute of Engineering and technology, Coimbatore. INDIA.

(2) PG Scholar, KPR Institute of Engineering and technology, Coimbatore. INDIA.

Received 27 May 2016; Accepted 28 June 2016; Available 12 July 2016

Address For Correspondence:

K. R. Sri Preethaa, Assistant Professor, KPR Institute of Engineering and technology, Coimbatore. INDIA.
Table 5: Socio-centric Method

Focus                          Example of
                               measures

Relationships                  Strength,
between actors                 confrimation,
                               multiplexity

Subgroups                      Social
                               cohesions,
                               structural
                               equivalence

Characteristic                 Size,density
of virtual
social network
COPYRIGHT 2016 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Preethaa, K.R. Sri; Radhika, M.
Publication:Advances in Natural and Applied Sciences
Date:Jun 30, 2016
Words:3518
Previous Article:Segmentation of tumor and edema of brain using neural networks.
Next Article:Detecting linear structures within the ASTER satellite image by effective denoising and contrast enhancement in the device independent color space.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters