Now showing 1 - 2 of 2
  • Publication
    Community Finding in Large Social Networks Through Problem Decomposition
    (University College Dublin. School of Computer Science and Informatics, 2008-08) ; ; ;
    The identification of cohesive communities is a key process in social network analysis. However, the algorithms that are effective for finding communities do not scale well to very large problems, as their time complexity is worse than linear in the number of edges in the graph. This is an important issue for those interested in applying social network analysis techniques to very large networks, such as networks of mobile phone subscribers. In this respect the contributions of this report are two-fold. First we demonstrate these scaling issues using a prominent community-finding algorithm as a case study. We then show that a twostage process, whereby the network is first decomposed into manageable subnetworks using a multilevel graph partitioning procedure, is effective in finding communities in networks with more than 106 nodes.
  • Publication
    Viewing the minimum dominating set and maximum coverage problems motivated by "word of mouth marketing" in a problem decomposition context
    (University College Dublin. School of Computer Science and Informatics, 2009) ; ;
    Modelling and analyzing the flow of influence is a key challenge in social network analysis. In scenarios where the network is too large to analyze in detail for computational reasons graph partitioning is a useful aid to decompose the large graph into manageable subgraphs. The question that arises in such a situation is how to partition a given graph such that the the solution obtained by combining the solutions from the individual subgraphs is as close as possible to the optimal solution obtained from the full graph (with respect to a particular objective). While graph cuts such as the min cut, ratio cut and normalised cut are a useful aid in breaking down the large problem into tractable subproblems, they may not yield the optimal graph partitioning with respect to a given objective. A natural question that arises in this scenario is “How close is the solution given by the graph cut to that of the optimal partitioning?” or in other words Are the above graph cuts good heuristics? In this report we pose the above questions with respect to two graph theoretic problems namely the minimum dominating set and maximum coverage. We partition the graphs using the normalised cut and present results that suggest that the normalised cut provides a “good partitioning” with respect to the defined objective.