Finding Pseudo-Cliques with Core Nodes Based on Formal Concept Analysis
Finding Pseudo-Cliques with Core Nodes Based on Formal Concept Analysis
复制标题
DOI：
10.1109/csci51800.2020.00058
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Yoshiaki Okubo
中科院分区：
文献类型：
--
作者：
Yoshiaki Okubo
本文给出了一个在给定的网络/图中寻找τ-伪团（一种稠密社区）的算法。τ-伪团定义为图中几个极大团的并，其核具有一定的椭圆度.虽然已经提出了一种检测这些伪团的算法，但由于该算法的计算过程相当复杂，其经验性能尤其是对于大型图来说并不令人满意，为了使这类伪团更实用，我们设计了一种新的算法，以帮助形式概念分析，一种分析关系数据的方法来检测它们。τ-伪团与形式概念之间的关系表明，伪团可以作为满足一定约束条件的形式概念而存在。他们的核心。在我们的基于FCA的算法中，我们可以享受简单的修剪规则的基础上定义的τ-伪团。从我们对几个基准网络和真实的网络的初步实验结果来看，该方法有望成为一种检测τ-伪团的有效方法.
In this paper, we present an algorithm for finding τ-pseudo cliques, a kind of dense communities, in a given network/graph. A τ-pseudo clique is defined as a union of several maximal cliques in the graph which has a certain degree of ovarlapness as its core. Although an algorithm for detecting those pseudo cliques has already been proposed, its empirical performance would not be acceptable particularly for large graphs because the computational procedure of the algorithm is rather complicated.In order to make this kind of pseudo-cliques more practical, we design a new algorithm for detecting them with the help of formal concept analysis, a method for analyzing relational data. A relationship between τ-pseudo cliques and formal concepts shows that pseudo cliques can be found as formal concepts satisfying a certain constraint w.r.t. their cores. In our FCA-based algorithm, we can enjoy simple pruning rules based on the definition of τ-pseudo cliques. From our preliminary experimental results for several benchmark and real networks, it is expected that the proposed method would be a promising approach to detecting τ-pseudo cliques.