IEEE Trans Cybern. 2018 May;48(5):1369-1382. doi: 10.1109/TCYB.2017.2693558. Epub 2017 Apr 25.
An attributed graph contains vertices that are associated with a set of attribute values. Mining clusters or communities, which are interesting subgraphs in the attributed graph is one of the most important tasks of graph analytics. Many problems can be defined as the mining of interesting subgraphs in attributed graphs. Algorithms that discover subgraphs based on predefined topologies cannot be used to tackle these problems. To discover interesting subgraphs in the attributed graph, we propose an algorithm called mining interesting subgraphs in attributed graph algorithm (MISAGA). MISAGA performs its tasks by first using a probabilistic measure to determine whether the strength of association between a pair of attribute values is strong enough to be interesting. Given the interesting pairs of attribute values, then the degree of association is computed for each pair of vertices using an information theoretic measure. Based on the edge structure and degree of association between each pair of vertices, MISAGA identifies interesting subgraphs by formulating it as a constrained optimization problem and solves it by identifying the optimal affiliation of subgraphs for the vertices in the attributed graph. MISAGA has been tested with several large-sized real graphs and is found to be potentially very useful for various applications.
有属性的图包含与一组属性值相关联的顶点。挖掘聚类或社区，即属性图中的有趣子图，是图分析中最重要的任务之一。许多问题都可以定义为挖掘属性图中的有趣子图。基于预定义拓扑结构发现子图的算法不能用于解决这些问题。为了发现有属性图中的有趣子图，我们提出了一种称为有属性图算法的挖掘有趣子图（MISAGA）的算法。MISAGA 通过首先使用概率度量来确定一对属性值之间的关联强度是否足够强来确定其是否有趣来执行其任务。给定有趣的属性值对，然后使用信息论度量计算每对顶点之间的关联度。基于每对顶点之间的边缘结构和关联度，MISAGA 通过将其表述为约束优化问题来识别有趣的子图，并通过确定属性图中顶点的子图的最佳隶属关系来解决该问题。MISAGA 已经在几个大型真实图上进行了测试，并且被发现对于各种应用非常有用。
