2012
Report
Open Access
DEMON: a local-first discovery method for overlapping communities
Coscia M., Rossetti G., Giannotti F., Pedreschi D.
Community discovery in complex networks is an interest- ing problem with a number of applications, especially in the knowledge extraction task in social and information net- works. However, many large networks often lack a particular community organization at a global level. In these cases, tra- ditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We pro- pose here a simple local-rst approach to community dis- covery, able to unveil the modular organization of real com- plex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighbor- hood, using a label propagation algorithm; nally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a lim- ited time complexity, so that it can be used on web-scale real networksSource: ISTI Technical reports, 2012
Project(s): DATA SIM
Coscia M., Rossetti G., Giannotti F., Pedreschi D.
Community discovery in complex networks is an interest- ing problem with a number of applications, especially in the knowledge extraction task in social and information net- works. However, many large networks often lack a particular community organization at a global level. In these cases, tra- ditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We pro- pose here a simple local-rst approach to community dis- covery, able to unveil the modular organization of real com- plex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighbor- hood, using a label propagation algorithm; nally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a lim- ited time complexity, so that it can be used on web-scale real networksSource: ISTI Technical reports, 2012
Project(s): DATA SIM
See at:
arxiv.org 
| ISTI Repository | CNR ExploRA
2012
Conference article
Open Access
Efficient distributed computation of human mobility aggregates through user mobility profiles
Nanni M., Trasarti R., Rossetti G., Pedreschi D.
A basic task of urban mobility management is the real-time monitoring of traffic within key areas of the territory, such as main entrances to the city, important attractors and possible bottlenecks. Some of them are well known areas, while while others can appear, disappear or simply change during the year, or even during the week, due for instance to roadworks, accidents and special events (strikes, demonstrations, concerts, new toll road fares). Especially in the latter cases, it would be useful to have a traffic monitoring system able to dynamically adapt to reference areas specified by the user. In this paper we propose and study a solution exploiting on-board location devices in private cars mobility, that continuously trace the position of the vehicle and periodically communicate it to a central station. Such vehicles provide a statistical sample of the whole population, and therefore can be used to compute a summary of the traffic conditions for the mobility manager. However, the large mass of information to be transmitted and processed to achieve that might be too much for a real-time monitoring system, the main problem being the systematic communication from each vehicle to a unique, centralized station. In this work we tackle the problem by adopting the general view of distributed systems for the computation of a global function, consisting in minimizing the amount of information communicated through a careful coordination of the single nodes (vehicles) of the system. Our approach involves the use of predictive models that allow the central station to guess (in most cases and within some given error threshold) the location of the monitored vehicles and then to estimate the density of key areas without communications with the nodes. © 2012 ACM.Source: ACM SIGKDD International Workshop on Urban Computing, pp. 87–94, Beijing, China, 12-16 August 2012
DOI: 10.1145/2346496.2346511
Metrics:
Nanni M., Trasarti R., Rossetti G., Pedreschi D.
A basic task of urban mobility management is the real-time monitoring of traffic within key areas of the territory, such as main entrances to the city, important attractors and possible bottlenecks. Some of them are well known areas, while while others can appear, disappear or simply change during the year, or even during the week, due for instance to roadworks, accidents and special events (strikes, demonstrations, concerts, new toll road fares). Especially in the latter cases, it would be useful to have a traffic monitoring system able to dynamically adapt to reference areas specified by the user. In this paper we propose and study a solution exploiting on-board location devices in private cars mobility, that continuously trace the position of the vehicle and periodically communicate it to a central station. Such vehicles provide a statistical sample of the whole population, and therefore can be used to compute a summary of the traffic conditions for the mobility manager. However, the large mass of information to be transmitted and processed to achieve that might be too much for a real-time monitoring system, the main problem being the systematic communication from each vehicle to a unique, centralized station. In this work we tackle the problem by adopting the general view of distributed systems for the computation of a global function, consisting in minimizing the amount of information communicated through a careful coordination of the single nodes (vehicles) of the system. Our approach involves the use of predictive models that allow the central station to guess (in most cases and within some given error threshold) the location of the monitored vehicles and then to estimate the density of key areas without communications with the nodes. © 2012 ACM.Source: ACM SIGKDD International Workshop on Urban Computing, pp. 87–94, Beijing, China, 12-16 August 2012
DOI: 10.1145/2346496.2346511
Metrics:
See at:
kdd.isti.cnr.it | dl.acm.org 
| doi.org | CNR ExploRA