An intense activity is nowadays devoted to the definition of models capturing the properties of complex networks. Among the most promising approaches, it has been proposed to model these graphs via their clique incidence bipartite graphs. However, this approach has, until now, severe limitations resulting from its incapacity to reproduce a key property of this object: the overlapping nature of cliques in complex networks. In order to get rid of these limitations we propose to encode the structure of clique overlaps in a network thanks to a process consisting in iteratively factorising the maximal bicliques between the upper level and the other levels of a multipartite graph. We show that the most natural definition of this factorising process leads to infinite series for some instances. Our main result is to design a restriction of this process that terminates for any arbitrary graph. Moreover, we show that the resulting multipartite graph has remarkable combinatorial properties and is closely related to another fundamental combinatorial object. Finally, we show that, in practice, this multipartite graph is computationally tractable and has a size that makes it suitable for complex network modelling.
翻译:目前,一项密集的活动是用来界定捕捉复杂网络特性的模型。在最有希望的方法中,有人提议通过这些图表的分类事件双片图示来模拟这些图表。然而,迄今为止,这一方法由于无法复制该对象的关键属性而受到严重限制:复杂网络中的晶体的重叠性质。为了消除这些局限性,我们提议在一个网络中编码分类重叠的结构,因为这是一个由迭代因素构成的过程,将多部分图的顶层与其他层次之间的最大两层相混合成。我们表明,这一因素化过程的最自然定义导致某些情况下的无限系列。我们的主要结果是设计出该过程的限制,以任何任意的图形结束。此外,我们表明,由此产生的多部分图具有显著的组合特性,并且与另一个基本的组合对象密切相关。最后,我们表明,在实践上,这一多部分图是可计算可移动的,并且有适合复杂网络建模的大小。