Node Similarity with q -Grams for Real-World Labeled Networks
Node Similarity with q -Grams for Real-World Labeled Networks
复制标题
DOI：
10.1145/3219819.3220085
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
A. Conte;Gaspare Ferraro;R. Grossi;Andrea Marino;K. Sadakane;T. Uno
中科院分区：
文献类型：
--
作者：
A. Conte;Gaspare Ferraro;R. Grossi;Andrea Marino;K. Sadakane;T. Uno
我们研究标记网络中的节点相似性，使用在有界长度q的路径中找到的标签序列。(This回想起基于Jaccard距离的文档相似性中使用的q-图。当应用于网络时，挑战是双重的：从标记路径生成的q-gram的数量随着q呈指数增长，并且应该考虑它们的频率：这导致了Jaccard指数的变化，称为Bray-Curtis指数。我们描述nSimGram，一套快速算法的节点相似性与q-gram，基于颜色编码，概率计数，草图和字符串算法，其中采样的元素的宇宙是指数的一种新的混合。我们提供的实验证据表明，我们的措施是有效的，我们的运行时间规模，以处理大型现实世界的网络。
We study node similarity in labeled networks, using the label sequences found in paths of bounded length q leading to the nodes. (This recalls the q-grams employed in document resemblance, based on the Jaccard distance.) When applied to networks, the challenge is two-fold: the number of q-grams generated from labeled paths grows exponentially with q, and their frequency should be taken into account: this leads to a variation of the Jaccard index known as Bray-Curtis index for multisets. We describe nSimGram, a suite of fast algorithms for node similarity with q-grams, based on a novel blend of color coding, probabilistic counting, sketches, and string algorithms, where the universe of elements to sample is exponential. We provide experimental evidence that our measure is effective and our running times scale to deal with large real-world networks.