Scholarlink

<p>Regular equivalence aims to identify nodes that have links to nodes that are themselves equivalent, and is considered to capture key relational properties in networks. Exact equivalences are notoriously difficult to emerge in real-world networks because of the rather stringent criteria required. This has motivated the development of approximate approaches, which, however, do not scale well to large networks. In this paper, we present a new method to compute approximate regular equivalences for weighted networks based on a partition refinement algorithm. This is parameterized by a tolerance <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41109_2025_726_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> </InlineEquation> that determines the extent to which two nodes may be deemed equivalent. We also show an asymptotic result for networks with power-law distribution that analytically provides a partition of approximately equivalent nodes. Using a number of benchmark networks, we show that our method outperforms the state of the art in terms of precision and running time. When the asymptotic partition is used to initialize the partition refinement algorithm for real-world networks, it avoids the problem of aggressive clustering that affects binary networks.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximate regular equivalence by partition refinement

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月27日

查看全文
  • Giuseppe Squillace,
  • Mirco Tribastone,
  • Max Tschaikowski,
  • Andrea Vandin

摘要

Regular equivalence aims to identify nodes that have links to nodes that are themselves equivalent, and is considered to capture key relational properties in networks. Exact equivalences are notoriously difficult to emerge in real-world networks because of the rather stringent criteria required. This has motivated the development of approximate approaches, which, however, do not scale well to large networks. In this paper, we present a new method to compute approximate regular equivalences for weighted networks based on a partition refinement algorithm. This is parameterized by a tolerance \(\varepsilon \) that determines the extent to which two nodes may be deemed equivalent. We also show an asymptotic result for networks with power-law distribution that analytically provides a partition of approximately equivalent nodes. Using a number of benchmark networks, we show that our method outperforms the state of the art in terms of precision and running time. When the asymptotic partition is used to initialize the partition refinement algorithm for real-world networks, it avoids the problem of aggressive clustering that affects binary networks.