Nyhetsflöde

Master Thesis Defense on "Exploring consensus-mediating arguments in online debates" (Thu, Oct 12Aug 28, 2:30p, 9:00am)

SuMonday 278 August 2017 at 09:00 - 10:30

Student: Adrian Ramirez¶

Date and Time: 14:30, Monday, 28th August 2017¶

Place: Ada Room, 4th floor¶

Examiner: Sarunas Gridzijauskas¶

Supervisor: Amira SolimanT¶

itle: Decentralized Diffusion-Controlled Algorithm for Community Detection¶

Opponents: Braulio Grana, Marco DallagiacomaAbstractCommunity detection in graphs has been an important research topic for many fields.  The aim of community detection is to extract from graphs those groups of nodes that present more connections between them than with the rest of the network. Extracting such groups at different scales can help understanding the global behaviour of the system.  However,  recent studies have shown that real-world  graphs  follow  power-law  distributions  for  degree  and  community  sizes.Specifically, these graphs present many small communities but just a few large ones.  This unbalanced community size distribution poses a great challenge for community detection algorithms.    Most  of  the  existing  methods  are  based  on  global  approaches  that  require information about the network to be processed as a whole. Thus, those techniques can not be applied when the graph is too big to fit into one single machine, or in distributed setting when the graph is portioned among multiple machines.  To solve this limitations a completely decentralized community detection algorithm is presented. It is based on diffusion, following a vertex-centric approach that let each node decide the diffusion rates based on local information. It adds as well a mechanism for controlling the diffusion speed through a customizable function.    We  evaluate  the  algorithm  with  a  variety  of  graphs  with  different  levels  of imbalance and community structures. Our algorithm is able to detect (almost)perfectly the communities when the imbalance between community sizes is not extreme. We show  as  well  how  the  sizes  of  the  detected  communities  can  be controlled  by  the  diffusion  strategy,  allowing  for  better detection  of  finer  or coarser resolutions in hierarchical graphs. The algorithm is also compared to other two well-known existing methods, achieving similar results in most of the cases though with a higher computation time.

SuMonday 278 August 2017 at 14:30 - 16:00

Student: Adrian Ramirez

Date and Time: 14:30, Monday, 28th August 2017

Place: Ada Room, 4th floor

Examiner: Sarunas Gridzijauskas

Supervisor: Amira SolimanT

Title: Decentralized Diffusion-Controlled Algorithm for Community Detection

Opponents: Braulio Grana, Marco DallagiacomaAbstractCommunity detection in graphs has been an important research topic for many fields.  The aim of community detection is to extract from graphs those groups of nodes that present more connections between them than with the rest of the network. Extracting such groups at different scales can help understanding the global behaviour of the system.  However,  recent studies have shown that real-world  graphs  follow  power-law  distributions  for  degree  and  community  sizes.Specifically, these graphs present many small communities but just a few large ones.  This unbalanced community size distribution poses a great challenge for community detection algorithms.    Most  of  the  existing  methods  are  based  on  global  approaches  that  require information about the network to be processed as a whole. Thus, those techniques can not be applied when the graph is too big to fit into one single machine, or in distributed setting when the graph is portioned among multiple machines.  To solve this limitations a completely decentralized community detection algorithm is presented. It is based on diffusion, following a vertex-centric approach that let each node decide the diffusion rates based on local information. It adds as well a mechanism for controlling the diffusion speed through a customizable function.    We  evaluate  the  algorithm  with  a  variety  of  graphs  with  different  levels  of imbalance and community structures. Our algorithm is able to detect (almost)perfectly the communities when the imbalance between community sizes is not extreme. We show  as  well  how  the  sizes  of  the  detected  communities  can  be controlled  by  the  diffusion  strategy,  allowing  for  better detection  of  finer  or coarser resolutions in hierarchical graphs. The algorithm is also compared to other two well-known existing methods, achieving similar results in most of the cases though with a higher computation time.

SuMonday 278 August 2017 at 10:30 - 12:00

SuMonday 278 August 2017 at 13:00 - 14:30