Abstract: 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 relationship 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 validates the effectiveness of the framework by performing extensive experiments, and discusses future works.

Key words:  multidimensional analysis, graph, link-based measure

摘要： 图数据无处不在，图中任意两个结点常常存在多种关系，各种不同关系组成不同结构的图，不同结构的图反映了个体之间不同的关系，同一网络中不同视角下对应的图的结构是不同的，这里视角表示关系或关系的组合。另一方面，图中一些典型的操作例如基于链接的相似度度量、可达性查询等依赖于图结构。因此不同视角下，这些操作的查询结果是不同的，为此提出了图数据上多维分析框架，并以视角有感知的链接关系下的top-k查询为例，验证了该多维分析框架的有效性。首先定义了多重图上偏向重要性的随机游走；然后给出了相应度量的上下界，利用上下界来有效进行top-k查询；最后在真实数据上进行了详细的分析，验证了图数据上多维分析框架的有效性，并对未来的研究进行了展望。

关键词: 多维分析, 图, 基于链接的度量