ROBUSTNESS OF DYNAMIC SOCIAL NETWORKS
Keywords:
Email Analysis, Cyclic Entropy, Cycles, Graphs, Directed, UndirectedAbstract
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
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.
