PaperlayerView exact revision on arXiv

Source-linked AI summary

GED: the method for group evolution discovery in social networks

Piotr Bródka, Stanisław Saganowski, Przemysław Kazienko

arXiv:1207.4297v2cs.SIphysics.soc-ph

TL;DR

The paper addresses the need to analyze how social groups evolve over time, a task for which existing group-evolution methods were considered incomplete or underdeveloped. It proposes GED, using an inclusion measure that combines member quantity and quality, and reports that experiments achieved the desired effects, with GED described as faster, more accurate, and more flexible than Asur et al.'s method.

  • Problem

    Methods for discovering and analyzing social-group evolution were still underdeveloped, despite strong interest in group extraction and evolution.

  • Method

    GED identifies group evolution using an inclusion measure based on group-member quantity and quality, with member quality represented through social position.

  • Results

    The experiments and comparisons achieved the desired effects, and the paper concludes that GED was faster, more accurate, and more flexible than Asur et al.'s method.

  • Takeaways & Limitations

    GED is designed to support both overlapping and non-overlapping groups while retaining low and adjustable computational complexity.

  • Takeaways & Limitations

    The inclusion measure is strict for non-identical groups because differing members reduce inclusion through both missing nodes and missing social-position values.

Abstract

from arXiv · show

The continuous interest in the social network area contributes to the fast development of this field. The new possibilities of obtaining and storing data facilitate deeper analysis of the entire network, extracted social groups and single individuals as well. One of the most interesting research topic is the dynamics of social groups, it means analysis of group evolution over time. Having appropriate knowledge and methods for dynamic analysis, one may attempt to predict the future of the group, and then manage it properly in order to achieve or change this predicted future according to specific needs. Such ability would be a powerful tool in the hands of human resource managers, personnel recruitment, marketing, etc. The social group evolution consists of individual events and seven types of such changes have been identified in the paper: continuing, shrinking, growing, splitting, merging, dissolving and forming. To enable the analysis of group evolution a change indicator - inclusion measure was proposed. It has been used in a new method for exploring the evolution of social groups, called Group Evolution Discovery (GED). The experimental results of its use together with the comparison to two well-known algorithms in terms of accuracy, execution time, flexibility and ease of implementation are also described in the paper.

1 Introduction

Social network analysis is increasingly important as expanding network systems and data access enable analysis of networks, groups, and individuals. The paper addresses the underdeveloped problem of discovering and analyzing group evolution by proposing GED and comparing it with existing methods.

  • Growing social networking systems and Internet use have increased the importance of social network analysis.
  • Social network analysis can examine entire networks, extracted social groups, and individual actors across diverse network contexts.
  • Group extraction and evolution attract substantial interest, but methods for discovering and analyzing group evolution remain underdeveloped.
  • The paper proposes Group Evolution Discovery (GED) and compares it with two other group-evolution discovery methods.
  • The paper introduces foundational concepts, presents GED, evaluates it experimentally, and concludes from the results.

2 Related work

Related work includes methods that track social-group changes using temporal comparisons, graph-based matching, or overlapping-community extraction. The paper focuses its evaluation on two existing approaches, including Asur et al. and Palla et al.'s clique-percolation method.

  • Social networks can be extracted from online, web-based, computer-supported, and virtual systems using communication or collaboration data.
  • Longitudinal data allow researchers to examine social networks in successive time snapshots and evaluate group changes over time.
  • Earlier work proposed GraphScope, FacetNet, nano-communities, and other approaches for tracking or investigating group evolution.
  • Asur et al. assign events by extracting groups in each time frame and comparing every possible pair in consecutive frames by size and overlap.
  • Palla et al. use clique percolation to permit overlapping groups, merge consecutive network frames, and match communities belonging to the same joined-graph group.

3 Group evolution discovery

The paper models social networks and group evolution across successive time frames, defining seven event types and introducing member-position-based measures for discovery. GED uses both group-member quantity and quality, with social position serving as a quality measure.

  • 3.1 Temporal social network: A temporal social network is an ordered list of time frames, each containing a separate social network.
  • 3.1 Temporal social network: Time frames may use consecutive, overlapping, or aggregated intervals depending on the analysis needs.
  • 3.2 Social group: No universally accepted definition of a social-network group exists; generally, groups have denser internal than external connections.
  • 3.3 Group evolution: The paper extends prior event lists to seven group-evolution types: continuing, shrinking, growing, splitting, merging, dissolving, and forming.
  • 3.4 Social position: GED evaluates both the quantity and quality of group members, using a centrality-based social-position measure to represent member quality.
  • 3.4 Social position: Social position can be computed for an entire network or restricted to members within a particular group.

4 GED: a method for group evolution discovery in the social network

GED discovers group evolution by comparing groups across consecutive time frames with an inclusion measure that combines member quantity and member importance. Its thresholds and event rules identify seven evolution types and allow group histories to be reconstructed.

  • GED is a method for discovering group evolution in social networks.
  • The inclusion measure evaluates how one group is included in another using member overlap and social-position contributions.Social position is defined for each node and may be replaced by another member-position measure such as degree centrality, betweenness, or PageRank.
  • GED balances group quantity and member quality, emphasizing both the portion of members retained and the contribution of important members.This favors groups containing many less-important members and groups containing fewer key members, while also incorporating relations through member positions.
  • GED compares each pair of groups in consecutive time frames, computes both directional inclusions, and assigns one event type using inclusions and group sizes.The procedure assumes one event per pair, although a group may participate in several events with different groups.
  • The method distinguishes continuing, shrinking, growing, splitting, merging, dissolving, and forming events through threshold-based rules.Parameters a and b adjust matching strictness for a particular social network and community-detection method; the authors suggest values from 50% to 100%.
  • A list of events between successive time frames can be combined to create the whole group evolution process.The paper illustrates a sequence involving forming, growing, splitting, shrinking, continuing, merging, and dissolving across eight time windows.

5 Experiments

The experiments use email-communication data from Wroclaw University of Technology organized into overlapping temporal windows. The source network contains thousands of nodes and over one hundred thousand email edges.

  • The experimental data come from Wroclaw University of Technology email communication collected from February 2006 to October 2007.
  • 5,845 nodes and 149,344 edges comprise the source email network.Nodes are distinct university email addresses, and edges represent emails sent from one address to another.
  • The temporal social network contains fourteen 90-day time frames with 45-day overlap between consecutive frames.The first frame spans days 1–90, while the second spans days 46–135.

5.1 Experiment based on overlapping groups extracted by CPM

The experiment compares GED with Asur et al. and Palla et al. on overlapping groups extracted by CPM, examining event detection, execution time, flexibility, and assignment.

  • Experimental setup: CPM extracted 80–136 groups per time window, averaging 112 groups with an average size of 19 nodes.The smallest group had 6 nodes and the largest had 613 nodes in time window 10.
  • Method by Asur et al.: Asur et al. identified 1,526 events, including 90 continuations, 18 forming, 29 dissolving, 703 merging, and 686 splitting events.The method required more than 5.5 h and used a 50% overlap threshold.
  • Method by Asur et al.: 128 anomalous cases represented 8% of Asur et al.’s results, reducing the number of distinct events to 1,398.Anomalies included simultaneous splitting and merging, or continuation combined with splitting or merging.
  • Method by Palla et al.: Palla et al. found 9,797 matched pairs, including 90 pairs with 100% overlap corresponding to continuation events in Asur et al.’s method.The method required additional group extractions and did not provide an algorithm for automatically assigning event types.
  • The GED method: GED’s total events decreased from 1,734 at 50% thresholds to 1,091 at 100% thresholds for a and b.The thresholds can filter highly overlapped results and adjust event detection to users’ needs; a mainly affects merging and b mainly affects splitting.
  • Comparison of methods: GED required less than 4 h for the full threshold table, with single runs taking less than 6 min and running over 50 times faster than Asur et al.’s method.With 50% thresholds, GED found 721 events absent from Asur et al.; at 10% thresholds, it omitted none of Asur et al.’s events.
  • Comparison of methods: GED’s inclusion thresholds address cases that Asur et al. may miss when successive groups differ by only one node.Asur et al.’s 100% continuation requirement prevents such cases from being treated as continuation, merging, or splitting under some conditions.
  • Comparison of methods: GED was reported as faster, more accurate, and more flexible than Asur et al., while its automatic event assignment made it more useful than Palla et al.’s manual analysis.Palla et al. found all matching pairs, whereas GED also found 308 forming and dissolving events missed by Palla et al.

5.2 Experiment based on disjoint groups extracted by Blondel

The Blondel-based experiment evaluates GED on disjoint groups, showing strong sensitivity to thresholds, faster execution than Asur et al., and broader event detection and grouping flexibility.

  • Comparison with Asur et al.: The Blondel-based results contained 40 anomalies, or 5% of all results, leaving 707 distinct events after removing them.The authors interpret this as suggesting that Asur et al.’s method works slightly better for disjoint groups.
  • GED results: GED identified 1,231 events at 50% thresholds and 663 at 100%, showing that thresholds a and b substantially affect event counts.Increasing either threshold reduced merging and splitting events linearly; GED also found 120 continuation events at both thresholds set to 100%.
  • GED flexibility: GED can be used with both overlapping and disjoint groups, unlike methods restricted to one grouping type.The paper presents this flexibility and adaptability as a major advantage of GED.
  • Execution time: A single Asur et al. run required almost 6 h, whereas a single GED run took about 13 min.GED required less than 8 h to calculate the full threshold table, while Asur et al.’s single run lasted almost 6 h.
  • Comparison with Asur et al.: At 50% thresholds, GED found 613 events that Asur et al.’s method did not recognize.The difference was attributed mainly to Asur et al.’s rigorous event-assignment conditions and limited flexibility; lowering GED thresholds recovered events it otherwise skipped.

6 Conclusions

The conclusion presents GED as a flexible method for identifying social-group evolution and reports that experiments against two existing methods achieved the paper’s desired effects.

  • Motivation: Social-group evolution analysis helps investigate the development and variability of groups over time.The conclusion frames this need as arising from the increasing number of systems in which people communicate.
  • GED method: GED combines group-member size and equivalence with members’ position and importance to identify changes between successive time frames.Its inclusion measure captures both the quantity and quality of group members.
  • GED method: GED supports overlapping and non-overlapping groups while retaining low, adjustable computational complexity.The method also permits different centrality indicators and uses two parameters, a and b, to provide control over its operation.
  • Conclusion: Experiments and comparisons with two existing methods led the authors to conclude that GED achieved the desired effects and may become a leading method for group evolution discovery.This is the paper’s stated conclusion from the experimental studies in Section 5.
Loading 1207.4297v2…