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 language | English |
---|---|
Pages (from-to) | 4646-4663 |
Number of pages | 18 |
Journal | IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING |
Volume | 36 |
Issue number | 9 |
DOIs | |
Publication status | Published - 2024 |
Keywords
- Approximation algorithms
- ego-network
- Heuristic algorithms
- Jaccard median
- Linear programming
- Mixed integer linear programming
- segmentation
- Social networking (online)
- Synthetic data
- Upper bound