Temporal Activity Path Based Character Correction in Heterogeneous Social Networks via Multimedia Sources

Jun Long, Lei Zhu, Zhan Yang, Chengyuan Zhang, Xinpan Yuan

TL;DR

This paper tackles the problem of character duplication in large-scale social networks, where the same person might be represented by multiple vertices due to name changes or anonymization. They propose a novel method using "Temporal Activity Paths" (TAPs) derived from multimedia social activities to measure character similarity and merge duplicate vertices, thereby improving the accuracy of social network analysis.

What Problem Does This Paper Address?

In today's digital world, social networks are built from vast amounts of multimedia data, leading to complex and massive graphs. A fundamental assumption in social network analysis is that each unique individual should be represented by a single vertex. However, this is often violated in practice due to factors like name changes, aliases, or anonymization, resulting in multiple vertices representing the same person. This "character duplication" or "name ambiguity" problem leads to significant inaccuracies in network analysis and mining. Existing methods often rely on external databases, which are not always available or sufficient in the context of large-scale, heterogeneous multimedia data. The challenge lies in accurately identifying and merging these duplicate character vertices without relying solely on explicit personal information.

Methods

The authors propose a novel approach to character correction by merging duplicate vertices. The core of their method involves:

  1. Building Relationship Networks: They first construct a relationship network among characters by extracting social activities from multimedia sources.
  2. Defining Temporal Activity Paths (TAPs): For each character, they define TAPs, which represent sequences of activities over time. These paths capture the temporal and structural aspects of a character's interactions.
  3. Measuring TAP Similarity: They then measure the similarity between the TAPs of any two characters. This similarity is calculated based on the temporal weights of relations and paths.
  4. Structure Error: A "structure error" metric is introduced to quantify the difference in network structure between vertices. Vertices with zero structure error are considered redundant candidates.
  5. Vertex Merging: If the TAP similarity between two characters is sufficiently high (above a defined threshold), they are considered to represent the same entity and are merged. This process aims to consolidate redundant information and improve character uniqueness.

Datasets

The paper mentions using a multimedia dataset for academic transaction networks, specifically extracting data from 724 proposals of the Natural Science Foundation of China (NSFC). This dataset consists of text-based information. They construct transaction activity networks from this data, resulting in a network with 598 vertices.

Key Insights and Ideas

  • Temporal Activity Paths (TAPs) as a Uniqueness Indicator: The key insight is that a person's unique pattern of activities over time, captured by TAPs, can serve as a strong indicator of their identity, even if their names differ.
  • Structure Error for Initial Candidate Identification: The "structure error" metric provides an initial way to identify potential duplicate vertices by looking for identical or very similar network neighborhoods.
  • TAP Similarity for Refined Uniqueness: While structure error can identify candidates, TAP similarity offers a more nuanced measure, incorporating temporal dynamics and activity patterns to confirm or refute uniqueness.
  • Heterogeneity and Temporality are Crucial: The authors emphasize that social networks are inherently heterogeneous (multiple vertex and relation types) and temporal, and their method leverages these aspects for more accurate character correction.

Key Results

The paper demonstrates that their proposed method can accurately confirm character uniqueness in large-scale social networks. While specific quantitative results like accuracy percentages are not explicitly detailed in the provided text, the experimental section describes how they applied their method to an academic transaction network. They identified pairs of vertices with zero structure error (e.g., Faye Wu and Fei Wu) and then used TAP similarity to further analyze them. The results indicated that some pairs with zero structure error were indeed unique (e.g., Shaojia Zhu and Shaonan Zhu) due to differences in temporal attributes, while others were highly similar and required merging.

Limitations and Future Work

  • Empirical Threshold Setting: The authors acknowledge that the similarity threshold used in their experiments was set empirically. They suggest that in future work, they will aim to compute the range of the threshold based on large amounts of network data and statistical techniques, and then design an adaptive adjustment algorithm for it.
  • Intellectualized Adaptive Adjustment: Currently, the threshold is not "intellectualized" or adaptively adjusted. Future work will focus on developing such adaptive mechanisms.

Summary updated

Abstract

Vast amount of multimedia data contains massive and multifarious social information which is used to construct large-scale social networks. In a complex social network, a character should be ideally denoted by one and only one vertex. However, it is pervasive that a character is denoted by two or more vertices with different names; thus it is usually considered as multiple, different characters. This problem causes incorrectness of results in network analysis and mining. The factual challenge is that character uniqueness is hard to correctly confirm due to lots of complicated factors, for example, name changing and anonymization, leading to character duplication. Early, limited research has shown that previous methods depended overly upon supplementary attribute information from databases. In this paper, we propose a novel method to merge the character vertices which refer to the same entity but are denoted with different names. With this method, we firstly build the relationship network among characters based on records of social activities participating, which are extracted from multimedia sources. Then we define temporal activity paths (TAPs) for each character over time. After that, we measure similarity of the TAPs for any two characters. If the similarity is high enough, the two vertices should be considered as the same character. Based on TAPs, we can determine whether to merge the two character vertices. Our experiments showed that this solution can accurately confirm character uniqueness in large-scale social network.
BibTeX
@inproceedings{long2018temporal,
  author = {Jun Long and Lei Zhu and Zhan Yang and Chengyuan Zhang and Xinpan Yuan},
  title = {{Temporal Activity Path Based Character Correction in Heterogeneous Social Networks via Multimedia Sources}},
  booktitle = {Adv. Multim},
  year = {2018},
  url = {https://openreview.net/forum?id=51ezBCE9Vss},
}
Figure