Regularities and dynamics in bisimulation reductions of big graphs

Y. Luo, G.H.L. Fletcher, A.J.H. Hidders, P.M.E. De Bra, Y. Wu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)

Samenvatting

Bisimulation is a basic graph reduction operation, which plays a key role in a wide range of graph analytical applications. While there are many algorithms dedicated to computing bisimulation results, to our knowledge, little work has been done to analyze the results themselves. Since data properties such as skew can greatly influence the performances of data-intensive tasks, the lack of such insight leads to inefficient algorithm and system design. In this paper we take a close look into various aspects of bisimulation results on big graphs, from both real-world scenarios and synthetic graph generators, with graph size varying from 1 million to 1 billion edges. We make the following observations: (1) A certain degree of regularity exists in real-world graphs' bisimulation results. Specifically, power-law distributions appear in many of the results' properties. (2) Synthetic graphs fail to fulfill one or more of these regularities that are revealed in the real-world graphs. (3) By examining a growing social network graph (Flickr-Grow), we see that the corresponding bisimulation partition relation graph grows as well, but the growth is stable with respect to the original graph.
Originele taal-2Engels
TitelFirst International Workshop on Graph Data Management Experiences and Systems (GRADES'13, New York NY, USA, June 23, 2013; co-located with SIGMOD/PODS'13)
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
Pagina's13/1-6
ISBN van geprinte versie978-1-4503-2188-4
DOI's
StatusGepubliceerd - 2013
Evenement1st International Workshop on Graph Data Management Experiences and Systems (GRADES 2013) - New York, Verenigde Staten van Amerika
Duur: 23 jun. 201323 jun. 2013
Congresnummer: 1

Congres

Congres1st International Workshop on Graph Data Management Experiences and Systems (GRADES 2013)
Verkorte titelGRADES 2013
Land/RegioVerenigde Staten van Amerika
StadNew York
Periode23/06/1323/06/13
AnderFirst International Workshop on Graph Data Management Experiences and Systems

Vingerafdruk

Duik in de onderzoeksthema's van 'Regularities and dynamics in bisimulation reductions of big graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit