{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/42231"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/42231","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Dynamic partitioning of social networks","abstract":"In this thesis, I study the problem of dynamic partitioning of online social networks (OSN). The problem is practically important since it lays the foundation of many applications. If OSN users are treated as vertices and their connections, like friendships or conversations, as edges, social networks can be represented as graphs. Partitioning the OSN graph itself is difficult as its power-law degree distribution leads to many cross-partition edges. Moreover, unlike traditional graphs, which are more static, OSN graphs often evolve significantly due to dynamic changes in social interactions and hence the social network can be viewed as a stream of graphs sampled at different time. Therefore, it is desirable to partition the graphs not only in the spatial dimension, but also in the time dimension, which makes the problem more difficult. However, these evolutions, like the changing of conversation frequency between two friends, are not totally random. Thus if these evolutions can be captured, predicted, and used properly, they will help us achieve better partitioning. As a result, we propose to make use of past graph evolution information and encode them into edge weights. We develop two corresponding methods: (1) weight the edges based on access frequency, assuming users involved in frequent conversations are more likely to stay in the same partition; or (2) weight the edges based on access recency, assuming a graph consisting mostly of newest edges will reflect the current status of the network. We then design two separate algorithms based on these two definitions of edge weights. Simulations show that each method captures desired graph characteristics respectively and achieves dynamic partitioning.","abstract_html":"In this thesis, I study the problem of dynamic partitioning of online social networks (OSN). The problem is practically important since it lays the foundation of many applications. If OSN users are treated as vertices and their connections, like friendships or conversations, as edges, social networks can be represented as graphs. Partitioning the OSN graph itself is difficult as its power-law degree distribution leads to many cross-partition edges. Moreover, unlike traditional graphs, which are more static, OSN graphs often evolve significantly due to dynamic changes in social interactions and hence the social network can be viewed as a stream of graphs sampled at different time. Therefore, it is desirable to partition the graphs not only in the spatial dimension, but also in the time dimension, which makes the problem more difficult. However, these evolutions, like the changing of conversation frequency between two friends, are not totally random. Thus if these evolutions can be captured, predicted, and used properly, they will help us achieve better partitioning. As a result, we propose to make use of past graph evolution information and encode them into edge weights. We develop two corresponding methods: (1) weight the edges based on access frequency, assuming users involved in frequent conversations are more likely to stay in the same partition; or (2) weight the edges based on access recency, assuming a graph consisting mostly of newest edges will reflect the current status of the network. We then design two separate algorithms based on these two definitions of edge weights. Simulations show that each method captures desired graph characteristics respectively and achieves dynamic partitioning.","abstract_has_math":false,"creators":["Yuan, Mindi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Lu, Yi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-02-03T19:28:40Z","date_published":"2013-02-03T19:28:40Z","updated_at":"2026-07-22T22:25:33Z","subjects":["Social networks","Partitioning","Online algorithms"],"languages":["en"],"rights":["Copyright 2012 Mindi Yuan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/42231","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lu, Yi"]},{"key":"dc:creator","label":"Author","values":["Yuan, Mindi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-02-03T19:28:40Z","2012-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Social networks","Partitioning","Online algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Mindi Yuan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/42231"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, I study the problem of dynamic partitioning of online social networks (OSN). The problem is practically important since it lays the foundation of many applications. If OSN users are treated as vertices and their connections, like friendships or conversations, as edges, social networks can be represented as graphs. Partitioning the OSN graph itself is difficult as its power-law degree distribution leads to many cross-partition edges. Moreover, unlike traditional graphs, which are more static, OSN graphs often evolve significantly due to dynamic changes in social interactions and hence the social network can be viewed as a stream of graphs sampled at different time. Therefore, it is desirable to partition the graphs not only in the spatial dimension, but also in the time dimension, which makes the problem more difficult. However, these evolutions, like the changing of conversation frequency between two friends, are not totally random. Thus if these evolutions can be captured, predicted, and used properly, they will help us achieve better partitioning. As a result, we propose to make use of past graph evolution information and encode them into edge weights. We develop two corresponding methods: (1) weight the edges based on access frequency, assuming users involved in frequent conversations are more likely to stay in the same partition; or (2) weight the edges based on access recency, assuming a graph consisting mostly of newest edges will reflect the current status of the network. We then design two separate algorithms based on these two definitions of edge weights. Simulations show that each method captures desired graph characteristics respectively and achieves dynamic partitioning.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-11-26T15:17:22Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 master thesis.rar: 11993634 bytes, checksum: 4a050dc719b409000473723d9f5486cf (MD5) Yuan_Mindi.pdf: 1742740 bytes, checksum: 15126416885effbf2c817f42d21f4497 (MD5)","Made available in DSpace on 2013-02-03T19:28:40Z (GMT). No. of bitstreams: 3 Mindi_Yuan.pdf: 1742740 bytes, checksum: 15126416885effbf2c817f42d21f4497 (MD5) master thesis.rar: 11993634 bytes, checksum: 4a050dc719b409000473723d9f5486cf (MD5) license.txt: 4058 bytes, checksum: 00e5d89c7283e10806791b80674a2b2d (MD5)"]},{"key":"dc:title","label":"Title","values":["Dynamic partitioning of social networks"]}]}],"canonical_facts":{"dc:contributor":["Lu, Yi"],"dc:creator":["Yuan, Mindi"],"dc:date":["2013-02-03T19:28:40Z","2012-12"],"dc:description":["In this thesis, I study the problem of dynamic partitioning of online social networks (OSN). The problem is practically important since it lays the foundation of many applications. If OSN users are treated as vertices and their connections, like friendships or conversations, as edges, social networks can be represented as graphs. Partitioning the OSN graph itself is difficult as its power-law degree distribution leads to many cross-partition edges. Moreover, unlike traditional graphs, which are more static, OSN graphs often evolve significantly due to dynamic changes in social interactions and hence the social network can be viewed as a stream of graphs sampled at different time. Therefore, it is desirable to partition the graphs not only in the spatial dimension, but also in the time dimension, which makes the problem more difficult. However, these evolutions, like the changing of conversation frequency between two friends, are not totally random. Thus if these evolutions can be captured, predicted, and used properly, they will help us achieve better partitioning. As a result, we propose to make use of past graph evolution information and encode them into edge weights. We develop two corresponding methods: (1) weight the edges based on access frequency, assuming users involved in frequent conversations are more likely to stay in the same partition; or (2) weight the edges based on access recency, assuming a graph consisting mostly of newest edges will reflect the current status of the network. We then design two separate algorithms based on these two definitions of edge weights. Simulations show that each method captures desired graph characteristics respectively and achieves dynamic partitioning.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-11-26T15:17:22Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 master thesis.rar: 11993634 bytes, checksum: 4a050dc719b409000473723d9f5486cf (MD5) Yuan_Mindi.pdf: 1742740 bytes, checksum: 15126416885effbf2c817f42d21f4497 (MD5)","Made available in DSpace on 2013-02-03T19:28:40Z (GMT). No. of bitstreams: 3 Mindi_Yuan.pdf: 1742740 bytes, checksum: 15126416885effbf2c817f42d21f4497 (MD5) master thesis.rar: 11993634 bytes, checksum: 4a050dc719b409000473723d9f5486cf (MD5) license.txt: 4058 bytes, checksum: 00e5d89c7283e10806791b80674a2b2d (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/42231"],"dc:language":["en"],"dc:rights":["Copyright 2012 Mindi Yuan"],"dc:subject":["Social networks","Partitioning","Online algorithms"],"dc:title":["Dynamic partitioning of social networks"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:33Z"}