A Framework For Community Identification in Dynamic Social Networks

author: Chayant Tantipathananandh, University of Illinois at Urbana-Champaign
published: Aug. 14, 2007,   recorded: August 2007,   views: 6823


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We propose frameworks and algorithms for identifying communities in social networks that change over time. Communities are intuitively characterized as “unusually densely knit” subsets of a social network. This notion becomes more problematic if the social interactions change over time. Aggregating social networks over time can radically misrepresent the existing and changing community structure. Instead, we propose an optimization-based approach for modeling dynamic community structure. We prove that finding the most explanatory community structure is NP-hard and APX-hard, and propose algorithms based on dynamic programming, exhaustive search, maximum matching, and greedy heuristics. We demonstrate empirically that the heuristics trace developments of community structure accurately for several synthetic and real-world examples.

See Also:

Download slides icon Download slides: kdd07_tantipathananandh_cidsn_01.ppt (3.0 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 tukta, August 21, 2007 at 3:34 p.m.:

my brother is the best forever !

Comment2 Lek, August 24, 2007 at 10:04 p.m.:

Nice talk. Keep up the good job!
เก่งนะเนี่ย มีความสามารถ น่าชื่นชมจริงๆ (ไม่ได้ชมใครบ่อยๆหรอกนะจ๊ะ)

Comment3 dtantiph, August 28, 2007 at 12:16 p.m.:

Good job, Gop

Comment4 ไม่ประสงค์ออกนาม, June 5, 2008 at 12:38 p.m.:

สุดยอดเลยครับได้ present ใน KDD ด้วย

Write your own review or comment:

make sure you have javascript enabled or clear this field: