A1397
Title: A commonality measure for overlapping clusters detections
Authors: Igor Kanovsky - Peres Academic Center (Israel) [presenting]
Dmitri Deinega - Bar-Ilan University (Israel)
Baruch Barzel - Bar-Ilan University (Israel)
Abstract: Network clustering is a challenging and practically important task. Most clustering algorithms assume that each node in a network belongs to a single cluster. However, in many real-world networks, such as social networks and classification tasks, clusters often overlap, allowing nodes to belong to multiple clusters simultaneously. Commonality between two nodes is defined as a function of their neighborhoods that evaluates to true if the nodes belong to the same cluster and false otherwise. For example, commonality may be defined as the ratio of mutual neighbors to the union of their neighborhoods exceeding a predefined threshold. Alternatively, commonality can be estimated using a neural network trained on a specific type of network. A set of three nodes with pairwise true commonality forms a hypernode. Two hypernodes are connected by a hyperlink if they share two nodes. Each connected component in the resulting hypergraph corresponds to a detected cluster, and clusters may overlap naturally. The proposed approach has two main advantages: locality, since cluster detection does not require information about the entire network, and stability, since the same communities remain identifiable even after random perturbations of a subset of network links.
