论文标题
在MMORPG图中查找使用层次图摘要的关键结构
Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization
论文作者
论文摘要
大型现实世界MMORPG（大量多人在线角色扮演游戏）中存在的关键结构是什么？如何考虑在不同层次结构级别的一致子结构，如何将带有层次节点标签的MMORPG图汇总？最近的MMORPG会在诱导每个实体具有层次标签的异质图的实体之间产生复杂的相互作用。简洁地总结异质MMORPG图对于更好地理解其结构至关重要。但是，这是一项具有挑战性的任务，因为它需要有效地处理复杂的交互和分层标签。尽管几乎没有总结大规模图的方法，但它们并未处理带有分层节点标签的异质图。我们提出了GSHL，这是一种新颖的方法，该方法总结了带有层次标签的异质图。我们使用MDL（最小描述长度）制定了层次标签的编码成本。 GSHL利用公式来识别和分段子图，并在图中发现紧凑且一致的结构。具有数百万边缘的大型现实世界MMORPG图上的实验表明，GSHL是一个有用且可扩展的工具，用于汇总该图，在图中找到重要而有趣的结构，并找到相似的用户。
What are the key structures existing in a large real-world MMORPG (Massively Multiplayer Online Role-Playing Game) graph? How can we compactly summarize an MMORPG graph with hierarchical node labels, considering consistent substructures at different levels of hierarchy? Recent MMORPGs generate complex interactions between entities inducing a heterogeneous graph where each entity has hierarchical labels. Succinctly summarizing a heterogeneous MMORPG graph is crucial to better understand its structure; however it is a challenging task since it needs to handle complex interactions and hierarchical labels efficiently. Although there exist few methods to summarize a large-scale graph, they do not deal with heterogeneous graphs with hierarchical node labels. We propose GSHL, a novel method that summarizes a heterogeneous graph with hierarchical labels. We formulate the encoding cost of hierarchical labels using MDL (Minimum Description Length). GSHL exploits the formulation to identify and segment subgraphs, and discovers compact and consistent structures in the graph. Experiments on a large real-world MMORPG graph with multi-million edges show that GSHL is a useful and scalable tool for summarizing the graph, finding important and interesting structures in the graph, and finding similar users.
