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 k segments. Each segment is represented by a summary network, and the goal is to minimize the total loss of representing k segments by k 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.

Ego-Network Segmentation via (Weighted) Jaccard Median

Loukides, Grigorios
;
Conte, Alessio;
2024-01-01

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 k segments. Each segment is represented by a summary network, and the goal is to minimize the total loss of representing k segments by k 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.
2024
Zhong, Haodi; Loukides, Grigorios; Conte, Alessio; Pissis, Solon P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1272611
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact