103 Downloads (Pure)

Abstract

An ego-network is a graph representing the interactions of a node (ego) with its neighbors and the interactions among those neighbors. A sequence of ego-networks having the same ego can thus model the evolution of these interactions over time. We introduce the problem of segmenting a sequence of ego-networks into kk segments. Each segment is represented by a summary network, and the goal is to minimize the total loss of representing kk segments by kk summaries. The main challenge is to construct a summary with minimum loss. To address it, we employ the Jaccard Median (JM) problem, for which, however, no effective and efficient algorithms are known. We develop several algorithms for JM: (I) an exact algorithm, based on Mixed Integer Linear Programming; (II) exact and approximation polynomial-time algorithms for minimizing an upper bound of the objective function of JM; and (III) efficient heuristics. We also study a generalization of the segmentation problem, in which there may be multiple edges between a pair of nodes in an ego-network, and develop a series of algorithms (exact algorithms and heuristics) for it, based on a more general problem than JM, called Weighted Jaccard Median (WJM). By building upon the above results, we design algorithms for segmenting a sequence of ego-networks. Extensive experiments show that our algorithms produce (near)-optimal solutions to JM or to WJM and that they substantially outperform state-of-the-art methods which can be employed for ego-network segmentation.

Original languageEnglish
Pages (from-to)4646-4663
Number of pages18
JournalIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume36
Issue number9
DOIs
Publication statusPublished - 2024

Keywords

  • Approximation algorithms
  • ego-network
  • Heuristic algorithms
  • Jaccard median
  • Linear programming
  • Mixed integer linear programming
  • segmentation
  • Social networking (online)
  • Synthetic data
  • Upper bound

Fingerprint

Dive into the research topics of 'Ego-Network Segmentation via (Weighted) Jaccard Median'. Together they form a unique fingerprint.

Cite this