ROBUSTNESS OF DYNAMIC SOCIAL NETWORKS

Authors

  • MAYTHAM SAFAR Computer Engineering Department, Kuwait University, Kuwait Al-Khaldiya, Kuwait City, Kuwait, Tel:+(965) 24987962
  • HISHAM FARAHAT Computer Engineering Department, Kuwait University, Kuwait Al-Khaldiya, Kuwait City, Kuwait, Tel:+(965) 24987412
  • KHALED MAHDI Chemical Engineering Department, Kuwait University, Kuwait Al-Khaldiya, Kuwait City, Kuwait, Tel:+(965) 24985618

Keywords:

Email Analysis, Cyclic Entropy, Cycles, Graphs, Directed, Undirected

Abstract

The cyclic entropy of a real virtual friendship network provides an insight on the degree of its robustness. Cyclic entropy depends on counting the number of cycles of different sizes in the network, in which a probability distribution function is resulted. Counting the number of cycles in the network is an NP problem. In this work we used a polynomial time approximation algorithm to count the number of cycles in an undirected graph that is based on regression and on a statistical mechanics approach. We used this approximation algorithm to analysis the dynamicity of a virtual social network, E-mail Messages Exchange Network (EMEN) where nodes and edges appear and disappear through time. We analyze the exact and approximated cyclic entropy variation with time as a function of the number of nodes and edges in the network. We further compare the cyclic entropy variation of the network to the traditional degree entropy variation. The purpose is to establish the robustness of the network. In addition, we study the effect of weighed links (number of interactions between users) on the analysis of such graphs. An actual friendship network is found to have cyclic entropy bounded between random and small-world networks models.

 

Downloads

Download data is not yet available.

References

R.Y. Shtykh, and Q. Jin (2008), Harnessing user contributions and dynamic profiling to better

satisfy individual information search needs, International Journal of Web and Grid Services, 4(1):

-79.

M. Safar, H. Farahat, and K. Mahdi (2009), Analysis of Dynamic Social Network: E-mail Massages

Exchange Network, Proceedings of the 11th International Conference on Information Integration

and Web-based Applications & Services (iiWAS).

K. Mahdi, H. Farahat, and M. Safar (2008), Temporal evolution of social networks in paltalk,

Proceedings of the 10th International Conference on Information Integration and Web-based Applications

and Services (iiWAS).

M. Safar, and H. B. Ghaith (2006), Friends Network, IADIS International Conference

WWW/Internet, Murcia, Spain.

S. Izumi, K. Yamanaka, Y. Tokairin, H. Takahashi, , and N. Shiratori (2009), Ubiquitous supervisory

system based on social contexts using ontology, Mobile Information Systems 5(2): 141-163.

G. Boella, L. Torre, and S. Villata (2009), Analyzing Cooperation in Iterative Social Network

Design, Journal of Universal Computer Science, Vol. 15, No. 13, pp. 2676-2700.

J.J. Macionis (2007), Sociology, Prentice Hall, 12 edition.

A. Bagchi, A. Bandyopadhyay, and S. Mitra (2006), Design of a data model for social network

applications. Journal of Database Management.

S. A. J. Shirazi (2006), Social Networking: Orkut, Facebook, and Gather, Blogcritics.

P. Boykin and V. Roychowdhury (2005), Leveraging social networks to fight spam, In IEEE

Computer Society Press, Computer, 38(4):61–68.

J. Xu, and H. Chen (2005), Criminal Network Analysis and Visualization, Communications of

the ACM, vol. 48, pp. 100 - 107.

T. Bhanu, S. M. A. Bagchi, and A. Bandyopadhyay (2006), Pre-processing and path normalization

of a web graph used as a social network, Special Issue on Web Information Retrieval of JDIM.

S. Mitra, A. Bagchi, and A. Bandyopadhyay (2006), Complex queries on web graph representing a

social network, 1st International Conference on Digital Information Management, pages 430–435.

K. Mahdi, M. Safar, and I. Sorkhoh (2008) Entropy of robust social networks, Proceedings of

IADIS International e-Society Conference.

M. Safar, K. Mahdi, and I. Sorkhoh (2008), Maximum Entropy of Fully Connected Social Network,

Proceedings of the International Association for Development of the Information Society (IADIS)

International Conference on Web Based Communities.

I. Sorkhoh, M. Safar, and K. Mahdi (2008), Classification of Social Networks, Proceedings of the

International Association for Development of the Information Society (IADIS) WWW/Internet

Conference.

B. Wang, H. Tang, C. Guo, and Z. Xiu (2005), Entropy optimization of scale-free networks

robustness to random failures, Physica A, vol. 363, Issue 2, pp. 591-596.

D. Simovici (2007), Metric-Entropy Pairs on Lattices, Journal of Universal Computer Science,

(11): 1767-1778.

R. Albert and A.-L. Barabasi (2002), Statistical mechanics of complex networks, Reviews of

Modern Physics, 74.

K. Mahdi, M. Safar, and H. Farahat (2009), Analysis of temporal evolution of social networks,

The Journal of Mobile Multimedia (JMM), 5(4):333–350.

E. Marinari, R. Monasson, and G. Semerjian (2006), An algorithm for counting circuits: application

to real world and random graphs, Europhysics Letters.

C. Hsinchun and X. Jennifer (2005), Criminal network analysis and visualization Communications

of ACM, pages 100–107.

J. Tyler, D. Wilkinson, and B. Huberman. Email as spectroscopy: Automated discovery of community

structure within organizations, Communities and Technologies, 6(3):81–96.

C. Cortes and D. Pregibon. Communities of interest, Intelligent Data Analysis, 6(3):211–219.

M. Newman, S. Forrest, and J. Balthrop (2002), Email networks and the spread of computer

viruses, Physics Reviews, 66(3).

R. Holzer, B. Malin, and L. Sweeney (2005), Email alias detection using social network analysis,

International Conference on Knowledge Discovery and Data Mining archive, Proceedings of the

rd international workshop on Link discovery.

R. Rowe, G. Creamer, S. Hershkop, and S. Stolfo (2007), Automated social hierarchy detection

through email network analysis, International Conference on Knowledge Discovery and Data

Mining archive.

G. Kossinets and D. J. Watts (2006), Empirical analysis of an evolving social network Science,

(5757):88–90.

G. Creamer, R. Rowe, S. Hershkop, and S. Stolfo (2009), Segmentation and automated social

hierarchy detection through email network analysis, Lecture Notes in Computer Science, Springer

Berlin / Heidelberg, Advances in Web Mining and Web Usage Analysis.

L. d. F. Costa, F. A. Rodrigues, G. Travieso, and P. R. Villas Boas (2007), Characterization of

Complex Networks: A survey of measurements, Advances in Physics, vol. 56, pp. 167 - 242.

R. Albert, H. Jeong, and A.-L. Barabasi (2000), Error and attack tolerance of complex networks,

Nature, vol. 406, pp. 378-382.

J. Scott (2000), Social Network Analysis: a Handbook, Sage Publication Ltd, 2nd edition.

W. Nooy, A. Mrvar, and V. Batagelj (2005), Exploratory Social Network Analysis with Pajek

(Structural Analysis in the Social Science). Cambridge University Press, England.

S. Wasserman and K. Faust (1994), Social Network Analysis: Methods and Applications. Cambridge

University Press, England.

G. D. Marco and L. Barolli (2007), On some current results of graph theory for ad-hoc networks,

Journal of Mobile Multimedia (JMM), 2(4):15–33.

D. B. Johnson, (1975) Finding all the elementary circuits of a directed graph, SIAM Journal on

Computing, pages 77–84.

K. Mahdi, M. Safar, I. Sarkhoh, and A. Kassem (2009), Cycle-Based versus Degree-based Classification

of Social Networks The Journal of Digital Information Management (JDIM), Volume 7,

No. 6, pp. 383-389.

M. Safar, K. Mahdi, H. Farahat, S. Albehairy, and A. Kassem (2010), Approximate Cycles

Count in Undirected Graphs The Journal of Digital Information Management (JDIM), (in press).

A. Hobson (1971), Concepts in Statistical Mechanics, Routledge, 1 edition.

P. D. L. Rios, S. Lise, and A. Pelizzola (2001), Bethe approximation for self-interacting lattice

trees, Europhysics Letters, 53:176–182.

O. Shental, P. H. Siegel, J. K. Wolf, D. Bickson, and D. Dolev (2008), Gaussian belief propagation

solver for systems of linear equations, The IEEE International Symposium on Information Theory,

Pages: 1863-1867.

M. Safar, K. Mahdi, and A. Kassim (2009), Universal cycles distribution function of social networks,

The First International Conference on Networked Digital Technologies (NDT).

V. Bhatnagar, S. Kaur, and L. Mignet (2009), A Parameterized Framework for Clustering Streams,

International Journal of Data Warehousing and Mining, 5(1): 36-56.

V. Nikulin (2008), Classification of Imbalanced Data with Random sets and Mean-Variance Filtering,

International Journal of Data Warehousing and Mining, 4(2): 63-78.

J. Luo, and X. Ni (2009), A clustering analysis and agent-based trust model in a grid environment

supporting virtual organisations, International Journal of Web and Grid Services, 5(1): 3-16.

Downloads

Published

2010-05-29

Issue

Section

Articles

Most read articles by the same author(s)