# Visualizing social network: a survey.

INTRODUCTIONSocial 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

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