CAJ | 학술논문

图数据无处不在,图中任意两个结点常常存在多种关系,各种不同关系组成不同结构的图,不同结构的图反映了个体之间不同的关系,同一网络中不同视角下对应的图的结构是不同的,这里视角表示关系或关系的组合.另一方面,图中一些典型的操作例如基于链接的相似度度量、可达性查询等依赖于图结构.因此不同视角下,这些操作的查询结果是不同的,为此提出了图数据上多维分析框架,并以视角有感知的链接关系下的top-k查询为例,验证了该多维分析框架的有效性.首先定义了多重图上偏向重要性的随机游走;然后给出了相应度量的上下界,利用上下界来有效进行top-k查询;最后在真实数据上进行了详细的分析,验证了图数据上多维分析框架的有效性,并对未来的研究进行了展望.
도수거무처불재,도중임의량개결점상상존재다충관계,각충불동관계조성불동결구적도,불동결구적도반영료개체지간불동적관계,동일망락중불동시각하대응적도적결구시불동적,저리시각표시관계혹관계적조합.령일방면,도중일사전형적조작례여기우련접적상사도도량、가체성사순등의뢰우도결구.인차불동시각하,저사조작적사순결과시불동적,위차제출료도수거상다유분석광가,병이시각유감지적련접관계하적top-k사순위례,험증료해다유분석광가적유효성.수선정의료다중도상편향중요성적수궤유주;연후급출료상응도량적상하계,이용상하계래유효진행top-k사순;최후재진실수거상진행료상세적분석,험증료도수거상다유분석광가적유효성,병대미래적연구진행료전망.
Graph data are ubiquitous. There exist different kinds of relationships between any two nodes. Different relationships can be modeled by different graphs, different graphs reflect different kinds of relationships between individuals. From different perspectives, the structure of the same network is different, where perspective denotes rela-tionship or union of relationship. On the other hand, the operators in the graph such as link-based measure, reachability query, rely on the structure of the graph. Therefore, this paper proposes the framework of multidimensional analysis on graph data, and uses a case study of perspective-aware link-based top-k query to verify the effectiveness of the framework. Firstly, this paper proposes importance biased random walk on multigraph. Then, this paper presents the corresponding upper/lower bounds, where the bounds are used to accelerate the query speed. At last, this paper vali-dates the effectiveness of the framework by performing extensive experiments, and discusses future works.