|Table of Contents|

Top-k Subgraph Query Algorithm on Uncertain Social Networks Based on Summary Graph

《南京理工大学学报》（自然科学版）[ISSN:1005-9830/CN:32-1397/N]

Issue:
2010年06期
Page:
738-743
Research Field:
Publishing date:

Info

Title:
Top-k Subgraph Query Algorithm on Uncertain Social Networks Based on Summary Graph
Author(s):
SHI Quan1; 2; XIAO Yang-hua3; LU Yi-qi3; WANG Heng-shan1
1.School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China;2.School of Computer Science and Technology,Nantong University,Nantong 226019,China;3.School of Computer Science,Fudan University,Shanghai 200433,China
Keywords:
social networks;  summary graphs;  Top-k query
PACS:
O157.5
DOI:
-
Abstract:
Aimed at the Top-k subgragh query problem for an uncertain Web social network,with the basic model of an undirected,vertex labeled and edge weighted simple graph,a summary graph is designed to represent social networks and encode the information of original graphs.The Top-k subgraph isomorphism query algorithm is proposed.Extensive experimental results from real and synthetic network data show: the operation time of the Top-k subgraph query algorithm based on summary graphs decreases compared with the VF2 algorithm;because the main foundation to construct a summary graph is the label of a vertex,the label distribution of a query graph has a great effect on the query performance;the query performance of the algorithm is improved by the index method with the increase of the vertex label number,but the query performance of the VF2 algorithm is not influenced;with the increase of the number of vertexes,compared with the VF2 algorithm,the increase of the time consumption of the algorithm is slow;the algorithm has stable and efficient performance on Top-k query.

References:

[ 1] Y an X F, Ph ilip S Y, H an JW. Graph index ing: Afrequent structure-based approach[ A] . Proceed ing s o fthe 2004 ACM S IGMOD Internationa l Conference onM anag em ent o f Data ( SIGMODc 04 ) [ C ]. Pa ris,Fance: ACM, 2004: 335- 346.
[ 2] Zhang S, HuM, Yang J. T reep:i A nove l graph indexing m ethod[ A]. Proceed ings of the 23rd Interna tionalCon fe rence on Data Eng ineering ( ICDEc07) [ C ].Istanbu,l Turkey: IEEE, 2007: 966- 975.
[ 3] Zhao P X, Yu J X, Yu P S. Graph index ing: tree +de lta> = graph[ A] . Proceedings o f the Internationa lCon ference on Very Large Data Bases ( VLDBc 07 )[ C] . V ienna, Austr ia: ACM, 2007: 938- 949.
[ 4] Fag in R, Lo tem A, NaorM. Optim a l aggrega tion a lgorithm s for m idd lew are [ J]. Journa l of Com pute r andSystem Sciences, 2003, 66( 4) : 614- 656.
[ 5] Chen C, Fredrikson C, Chr istodorescuM. M ining graphpatterns effic iently v ia random ized summ aries[ A]. Proceedings of the International Conference on Very LargeData Bases( VLDBc09) [ C]. Lyon, France: VLDB Endowmen,t 2009: 742- 753.
[ 6] Corde lla LP, Fogg ia P, Sansone C, e t a.l A ( Sub)g raph isom orph ism a lgor ithm form atch ing larg e g raphs[ J] . Journa l of Pattern Ana lysis andM ach ine Inte ll-igence, 2004, 26( 10): 1367- 1372

Memo

Memo:
-
Last Update: 2012-11-02