#### DMCA

## Multi-Step Community Detection and Hierarchical Time Segmentation in Evolving Networks (2011)

Venue: | Proc. of the 5th SNA-KDD Workshop Social Network Mining and Analysis, August 21 |

Citations: | 7 - 0 self |

### Citations

3912 | 15). Emergence of scaling in random networks
- Barabási, Albert
- 1999
(Show Context)
Citation Context ...eadth first search fashion. This is not a social networks, but our algorithms and definitions are valid on any kind of evolving graphs and internet topology share many properties with social networks =-=[35, 5]-=-. Thus we consider it as another interesting dataset and include it in our study. The measurement has been performed during several years, yielding a dynamic map of the multicast routers topology. For... |

3313 |
Collective dynamics of ‘small-world’ networks
- Watts, Strogatz
- 1998
(Show Context)
Citation Context ...eadth first search fashion. This is not a social networks, but our algorithms and definitions are valid on any kind of evolving graphs and internet topology share many properties with social networks =-=[35, 5]-=-. Thus we consider it as another interesting dataset and include it in our study. The measurement has been performed during several years, yielding a dynamic map of the multicast routers topology. For... |

1474 |
Finding and evaluating community structure in networks
- Newman, Girvan
(Show Context)
Citation Context ...a lot of interest and many algorithms have been proposed. Usually, people try to find a partition pi of the nodes which can be evaluated by a quality function that gives a score to pi. The modularity =-=[20]-=- is a widely used quality function which compares, for each community, the proportion of links inside the community with a null model claiming that meaningful communities are more densely connected th... |

813 | Community detection in graphs
- Fortunato
- 2010
(Show Context)
Citation Context ...e last decade, many definitions have formalized this concept and many algorithms have been proposed to compute these communities in large graphs using only topological information in an efficient way =-=[12, 25, 27]-=-. The Louvain Method [7] in particular allows to detect communities quickly and efficiently with enlightening results. Complex networks model systems that are usually evolving (pages appear or disappe... |

586 | Fast unfolding of communities in large networks
- Blondel, Guillaume, et al.
(Show Context)
Citation Context ...ave formalized this concept and many algorithms have been proposed to compute these communities in large graphs using only topological information in an efficient way [12, 25, 27]. The Louvain Method =-=[7]-=- in particular allows to detect communities quickly and efficiently with enlightening results. Complex networks model systems that are usually evolving (pages appear or disappear on the web, contacts ... |

489 | Group formation in large social networks: Membership, growth, and evolution
- Backstrom, Huttenlocher, et al.
- 2006
(Show Context)
Citation Context ...of the modeled systems. For instance, the detection of these communities can be used for graph visualization [2] or to mine various kinds of graphs: they can be groups of interest in a social network =-=[4, 33]-=-, web pages dealing with the same subject [10], proteins that share a common function in a metabolic network [36] or modules in a software source code [18]. In the last decade, many definitions have f... |

309 |
Resolution limit in community detection
- Fortunato, Barthélemy
- 2007
(Show Context)
Citation Context ...nce the modularity is null when all nodes are grouped in a single community, interesting modularities are always positive and the higher the modularity, the better the partition. Readers can refer to =-=[6]-=- for tighter bounds and a more precise study of the modularity and to [26] for expected values on random graphs. The modularity’s main drawback is that it favors large communities [6]. However, it is ... |

270 | Pocket switched networks and human mobility in conference environments
- Hui, Chaintreau, et al.
- 2005
(Show Context)
Citation Context ...lowed us to weight snapshots with the effective duration between them. Note that the graph is very stable during night, with only a few connections, and very dynamic during days. For more details see =-=[15]-=-. The three graphs have very different characteristics. Mrinfo and Blogs are quite stable and Imote is very dynamic; Imote contains many snapshots and Blogs only a few. Finally, Blogs is growing (no l... |

213 |
Graph clustering
- Schaeffer
- 2007
(Show Context)
Citation Context ...e last decade, many definitions have formalized this concept and many algorithms have been proposed to compute these communities in large graphs using only topological information in an efficient way =-=[12, 25, 27]-=-. The Louvain Method [7] in particular allows to detect communities quickly and efficiently with enlightening results. Complex networks model systems that are usually evolving (pages appear or disappe... |

167 | Using automatic clustering to produce high-level system organizations of source code. In:
- Mancoridis, Mitchell, et al.
- 1998
(Show Context)
Citation Context ...be groups of interest in a social network [4, 33], web pages dealing with the same subject [10], proteins that share a common function in a metabolic network [36] or modules in a software source code =-=[18]-=-. In the last decade, many definitions have formalized this concept and many algorithms have been proposed to compute these communities in large graphs using only topological information in an efficie... |

154 | Graphscope: parameter-free mining of large time-evolving graphs
- Sun, Faloutsos, et al.
- 2007
(Show Context)
Citation Context ... Finally, extracting interesting time windows based on structural changes has attracted attention mainly to perform event detection by studying how much new information is brought by the new snapshot =-=[30]-=- and by discovering correlated spatio-temporal changes [9]. We will extend the notion of time windows to a hierarchy of windows that do not have to be consecutive in section 4, based on our notion of ... |

131 |
Evolutionary clustering
- Chakrabarti, Kumar, et al.
- 2006
(Show Context)
Citation Context ...ithms like streaming algorithms [22], modification of static algorithms [3], use of new objects like sliced networks [19] and finally new definitions of communities [31]. A new definition proposed in =-=[16]-=- splits the quality function in two terms: one for the quality of a snapshot partition and one for the stability. It can be quickly summarized in defining the quality Qdyn as Qdyn = Qsnapshot+αQstabil... |

125 | Quantifying social group evolution
- Palla, Barabasi, et al.
- 2007
(Show Context)
Citation Context ...tuitive method is to compare two communities of consecutive time steps with rules based on the size of their intersection [1, 14, 29]. These rules can be used conjointly with the clustering algorithm =-=[23]-=- or simplified by tracking only specific core nodes such as the ones defined in [34] which would be more representative of their community than others. Many workarounds are required because of stabili... |

113 | A framework for community identification in dynamic social networks
- Tantipathananandh, Berger-Wolf, et al.
- 2007
(Show Context)
Citation Context ...ilistic models [32], modified algorithms like streaming algorithms [22], modification of static algorithms [3], use of new objects like sliced networks [19] and finally new definitions of communities =-=[31]-=-. A new definition proposed in [16] splits the quality function in two terms: one for the quality of a snapshot partition and one for the stability. It can be quickly summarized in defining the qualit... |

94 | An event-based framework for characterizing the evolutionary behavior of interaction graphs
- Asur, Parthasarathy, et al.
- 2007
(Show Context)
Citation Context ...able, split, appear, disappear, or merge with another one for instance. The intuitive method is to compare two communities of consecutive time steps with rules based on the size of their intersection =-=[1, 14, 29]-=-. These rules can be used conjointly with the clustering algorithm [23] or simplified by tracking only specific core nodes such as the ones defined in [34] which would be more representative of their ... |

92 | Community structure in time-dependent, multiscale, and multiplex networks.
- Mucha, Richardson, et al.
- 2010
(Show Context)
Citation Context ...nt techniques have been proposed, such as probabilistic models [32], modified algorithms like streaming algorithms [22], modification of static algorithms [3], use of new objects like sliced networks =-=[19]-=- and finally new definitions of communities [31]. A new definition proposed in [16] splits the quality function in two terms: one for the quality of a snapshot partition and one for the stability. It ... |

91 | Evolutionary spectral clustering by incorporating temporal smoothness
- Chi, Song, et al.
- 2007
(Show Context)
Citation Context ...Qsnapshot is a static quality function, modularity for instance, Qstability is a stability term and α is a parameter that allows changing the importance of the stability. Instead of a stability term, =-=[28]-=- extends this idea and proposes to add an overall quality term. The partition found at time t does not have to be close to the partition at time t − 1 but must be a good partition at time t and a fair... |

90 |
Multiscale visualization of small world networks
- Auber, Chiricota, et al.
- 2003
(Show Context)
Citation Context ...nderstanding this underlying structure may have a major impact in the global understanding of the modeled systems. For instance, the detection of these communities can be used for graph visualization =-=[2]-=- or to mine various kinds of graphs: they can be groups of interest in a social network [4, 33], web pages dealing with the same subject [10], proteins that share a common function in a metabolic netw... |

80 |
Tracking evolving communities in large linked networks
- Hopcroft, Khan, et al.
- 2004
(Show Context)
Citation Context ...able, split, appear, disappear, or merge with another one for instance. The intuitive method is to compare two communities of consecutive time steps with rules based on the size of their intersection =-=[1, 14, 29]-=-. These rules can be used conjointly with the clustering algorithm [23] or simplified by tracking only specific core nodes such as the ones defined in [34] which would be more representative of their ... |

66 | 2006) “Monic: Modeling and Monitoring Cluster Transitions
- Spiliopoulou, Ntoutsi, et al.
(Show Context)
Citation Context ...able, split, appear, disappear, or merge with another one for instance. The intuitive method is to compare two communities of consecutive time steps with rules based on the size of their intersection =-=[1, 14, 29]-=-. These rules can be used conjointly with the clustering algorithm [23] or simplified by tracking only specific core nodes such as the ones defined in [34] which would be more representative of their ... |

65 |
Community structure in directed networks
- Leicht, Newman
- 2008
(Show Context)
Citation Context ...rs large communities [6]. However, it is very natural for studying graph structure and it can be easily extended to more complex cases, such as directed or weighted graphs and overlapping communities =-=[17, 21]-=-. Finding the partition that maximizes the modularity on a given graph is NP-hard and many approximation algorithms have been proposed (see [12, 25, 27] for very complete surveys). Modularity is one o... |

48 | Analyzing Communities and Their Evolutions in Dynamic Social Networks.
- Lin, Chi, et al.
- 2009
(Show Context)
Citation Context ...es [14] or use a very constrained algorithm [23]. The second approach consists in directly integrating time into the computation. Different techniques have been proposed, such as probabilistic models =-=[32]-=-, modified algorithms like streaming algorithms [22], modification of static algorithms [3], use of new objects like sliced networks [19] and finally new definitions of communities [31]. A new definit... |

40 | Extending the definition of modularity to directed graphs with overlapping communities
- Nicosia, Mangioni, et al.
- 2009
(Show Context)
Citation Context ...rs large communities [6]. However, it is very natural for studying graph structure and it can be easily extended to more complex cases, such as directed or weighted graphs and overlapping communities =-=[17, 21]-=-. Finding the partition that maximizes the modularity on a given graph is NP-hard and many approximation algorithms have been proposed (see [12, 25, 27] for very complete surveys). Modularity is one o... |

27 | Incremental spectral clustering with application to monitoring of evolving blog communities
- Ning, Xu, et al.
- 2007
(Show Context)
Citation Context ...e second approach consists in directly integrating time into the computation. Different techniques have been proposed, such as probabilistic models [32], modified algorithms like streaming algorithms =-=[22]-=-, modification of static algorithms [3], use of new objects like sliced networks [19] and finally new definitions of communities [31]. A new definition proposed in [16] splits the quality function in ... |

22 | Structural and temporal analysis of the blogosphere through community factorization
- Chi, Zhu, et al.
- 2007
(Show Context)
Citation Context ...on of these communities can be used for graph visualization [2] or to mine various kinds of graphs: they can be groups of interest in a social network [4, 33], web pages dealing with the same subject =-=[10]-=-, proteins that share a common function in a metabolic network [36] or modules in a software source code [18]. In the last decade, many definitions have formalized this concept and many algorithms hav... |

22 |
Hierarchical modularity of nested bowties in metabolic networks
- Zhao, Yu, et al.
- 2006
(Show Context)
Citation Context ...to mine various kinds of graphs: they can be groups of interest in a social network [4, 33], web pages dealing with the same subject [10], proteins that share a common function in a metabolic network =-=[36]-=- or modules in a software source code [18]. In the last decade, many definitions have formalized this concept and many algorithms have been proposed to compute these communities in large graphs using ... |

18 | Extracting intra-domain topology from mrinfo probing
- Pansiot, Mérindol, et al.
- 2010
(Show Context)
Citation Context ...ing dataset and include it in our study. The measurement has been performed during several years, yielding a dynamic map of the multicast routers topology. For more details about the measurement, see =-=[24]-=-. We focus here on year 2005, which represents 365 snapshots containing about 3100 nodes on average. The evolution of this graph is divided in three very distinct phases. The first phase spans from th... |

13 | Discovering correlated spatio-temporal changes in evolving graphs
- Chan, Bailey, et al.
- 2008
(Show Context)
Citation Context ...ctural changes has attracted attention mainly to perform event detection by studying how much new information is brought by the new snapshot [30] and by discovering correlated spatio-temporal changes =-=[9]-=-. We will extend the notion of time windows to a hierarchy of windows that do not have to be consecutive in section 4, based on our notion of multistep communities. 2. MULTI-STEP COMMUNITIES 2.1 Defin... |

13 |
A new approach for detecting scientific specialties from raw cocitation networks.
- Wallace, Gingras, et al.
- 2009
(Show Context)
Citation Context ...of the modeled systems. For instance, the detection of these communities can be used for graph visualization [2] or to mine various kinds of graphs: they can be groups of interest in a social network =-=[4, 33]-=-, web pages dealing with the same subject [10], proteins that share a common function in a metabolic network [36] or modules in a software source code [18]. In the last decade, many definitions have f... |

12 | Static community detection algorithms for evolving networks
- Aynaud, Guillaume
- 2010
(Show Context)
Citation Context ...ntegrating time into the computation. Different techniques have been proposed, such as probabilistic models [32], modified algorithms like streaming algorithms [22], modification of static algorithms =-=[3]-=-, use of new objects like sliced networks [19] and finally new definitions of communities [31]. A new definition proposed in [16] splits the quality function in two terms: one for the quality of a sna... |

10 | Socio-semantic dynamics in a blog network
- Cointet, Roth
(Show Context)
Citation Context ...t with an empty graph and every day we add the blogs and links seen this day. The obtained evolving graph grows slowly and regularly during 120 time steps. For more details about the measurement, see =-=[11]-=-. Mrinfo dataset. The second graph represents the topology of multicast routers on the Internet measured with the mrinfo tool. This tool allows asking to a multicast router all its neighboring multica... |

9 | When are networks truly modular
- Reichardt, Bornholdt
(Show Context)
Citation Context ...ty, interesting modularities are always positive and the higher the modularity, the better the partition. Readers can refer to [6] for tighter bounds and a more precise study of the modularity and to =-=[26]-=- for expected values on random graphs. The modularity’s main drawback is that it favors large communities [6]. However, it is very natural for studying graph structure and it can be easily extended to... |

6 |
Maximizing Modularity is hard. ArXiv Physics eprints
- Brandes, Delling, et al.
- 2006
(Show Context)
Citation Context ...modularity, which applies on evolving graphs and is defined on several snapshots. Detecting communities means finding a partition that maximizes the average modularity. As it is a NP-complete problem =-=[8]-=-, we will actually try to find partitions that have the higher average modularity possible. 2.2 Detection algorithms We propose two algorithms to find a partition of high average modularity on a given... |

4 | Community Evolution of Social Network: Feature, Algorithm and Model
- Wang, Wu, et al.
(Show Context)
Citation Context ...sed on the size of their intersection [1, 14, 29]. These rules can be used conjointly with the clustering algorithm [23] or simplified by tracking only specific core nodes such as the ones defined in =-=[34]-=- which would be more representative of their community than others. Many workarounds are required because of stability issues: the static algorithms used on each snapshot are often non-stable and henc... |