Efficient Community Re-creation in Multilayer Networks Using Boolean Operations
Efficient Community Re-creation in Multilayer Networks Using Boolean Operations
复制标题
使用布尔运算在多层网络中高效重建社区
DOI：
10.1016/j.procs.2017.05.246
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Chakravarthy, Sharma
中科院分区：
文献类型：
--
作者：
Santra, Abhishek;Bhowmick, Sanjukta;Chakravarthy, Sharma
网络是相互关联的实体系统的有用数学表示。在实体可以通过不同因素关联的情况下，模型可以扩展以形成网络的网络或多层网络。然而，随着层数的增加，分析多层网络的成本会越来越高。我们解决了在多层网络中有效查找社区的问题。社区是紧密连接的实体组，表明组中的实体是相似的。在这里，我们证明，给定某些易于验证的结构条件（我们称之为自我保护社区），我们可以使用基本的布尔运算来组合从每个网络层获得的社区，以获得整个多层网络上的社区。当我们的方法应用于现实世界的数据集（例如交通事故）时，我们可以将在多层网络中查找社区的时间减少 40% 以上。我们提出的技术为多层网络的新兴领域做出了一些重要贡献。我们提出了一种优雅且低成本的方法来组合多个层的结果，而无需重新计算组合层。我们的方法还使得在各个层添加和处理新信息变得更加容易。总之，我们的方法通过处理多种数据类型来解决大数据的多样性问题，并通过实现对来自多个网络的数据的快速分析来解决数据量方面的问题。
Networks are useful mathematical representations of systems of interrelated entities. In cases where the entities can be related via different factors, the models can be extended to form networks of networks or multilayer networks. However, analyzing multilayer networks can get increasingly more expensive as the number of layers increase.We address the problem of efficiently finding communities in multilayer networks. Communities are groups of tightly connected entities that indicate that entities in the group are similar. Here we demonstrate that given certain easily verifiable structural conditions, which we term as self preserving communities, we can use fundamental Boolean operations to combine the communities obtained from each network layer to obtain the communities over the entire multilayer network. Our approach, when applied to real-world datasets such as traffic accidents, shows that we can reduce the time to find communities in multilayer networks by over 40%.Our proposed technique makes several important contributions to the nascent area of multilayer networks. We present an elegant and low-cost method to combine results from multiple layers, without recomputing the combined layers. Our method also makes it easier to add and process new information at individual layers. Together, our approach addresses both the variety aspect of big data by handling multiple data types as well as the volume aspect by enabling fast analysis of data from multiple networks.