2017
Contribution to book
Open Access
Dynamic Community Detection
Cazabet R, Rossetti G, Amblard F
Community detection is one of the most popular topics in the field of network analysis. Since the seminal paper of Girvan and Newman (2002), hundreds of papers have been published on the topic. From the initial problem of graph partitioning, in which each node of the network must belong to one and only one community, new aspects of community structures have been taken into consideration, such as overlapping communities and hierarchical decomposition. Recently, new methods have been proposed, which can handle dynamic networks. The communities found by these algorithms are called dynamic communities.DOI: 10.1007/978-1-4614-7163-9_383-1
DOI: 10.1007/978-1-4939-7131-2_383
Metrics:
Cazabet R, Rossetti G, Amblard F
Community detection is one of the most popular topics in the field of network analysis. Since the seminal paper of Girvan and Newman (2002), hundreds of papers have been published on the topic. From the initial problem of graph partitioning, in which each node of the network must belong to one and only one community, new aspects of community structures have been taken into consideration, such as overlapping communities and hierarchical decomposition. Recently, new methods have been proposed, which can handle dynamic networks. The communities found by these algorithms are called dynamic communities.DOI: 10.1007/978-1-4614-7163-9_383-1
DOI: 10.1007/978-1-4939-7131-2_383
Metrics:
See at:
hal.archives-ouvertes.fr 
| doi.org 
| doi.org | Hyper Article en Ligne | CNR IRIS | CNR IRIS
2017
Conference article
Restricted
NDlib: Studying network diffusion dynamics
Rossetti G, Milli L, Rinzivillo S, Sirbu A, Pedreschi D, Giannotti F
Nowadays the analysis of diffusive phenomena occurring on top of complex networks represents a hot topic in the Social Network Analysis playground. In order to support students, teachers, developers and researchers in this work we introduce a novel simulation framework, NDlib. NDlib is designed to be a multi-level ecosystem that can be fruitfully used by different user segments. Upon the diffusion library, we designed a simulation server that allows remote execution of experiments and an online visualization tool that abstract the programmatic interface and makes available the simulation platform to non-technicians.DOI: 10.1109/dsaa.2017.6
Project(s): CIMPLEX
, SoBigData
Metrics:
Rossetti G, Milli L, Rinzivillo S, Sirbu A, Pedreschi D, Giannotti F
Nowadays the analysis of diffusive phenomena occurring on top of complex networks represents a hot topic in the Social Network Analysis playground. In order to support students, teachers, developers and researchers in this work we introduce a novel simulation framework, NDlib. NDlib is designed to be a multi-level ecosystem that can be fruitfully used by different user segments. Upon the diffusion library, we designed a simulation server that allows remote execution of experiments and an online visualization tool that abstract the programmatic interface and makes available the simulation platform to non-technicians.DOI: 10.1109/dsaa.2017.6
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
doi.org | CNR IRIS | ieeexplore.ieee.org | Archivio istituzionale della Ricerca - Scuola Normale Superiore | CNR IRIS
2017
Journal article
Open Access
RDyn: graph benchmark handling community dynamics
Rossetti G
Graph models provide an understanding of the dynamics of network formation and evolution; as a direct consequence, synthesizing graphs having controlled topology and planted partitions has been often identified as a strategy to describe benchmarks able to assess the performances of community discovery algorithm. However, one relevant aspect of real-world networks has been ignored by benchmarks proposed so far: community dynamics. As time goes by network communities rise, fall and may interact with each other generating merges and splits. Indeed, during the last decade dynamic community discovery has become a very active research field: in order to provide a coherent environment to test novel algorithms aimed at identifying mutable network partitions we introduce RDYN, an approach able to generates dynamic networks along with time-dependent ground-truth partitions having tunable quality.Source: JOURNAL OF COMPLEX NETWORKS (ONLINE), vol. 5 (issue 6), pp. 893-912
DOI: 10.1093/comnet/cnx016
Project(s): CIMPLEX, SoBigData
Metrics:
Rossetti G
Graph models provide an understanding of the dynamics of network formation and evolution; as a direct consequence, synthesizing graphs having controlled topology and planted partitions has been often identified as a strategy to describe benchmarks able to assess the performances of community discovery algorithm. However, one relevant aspect of real-world networks has been ignored by benchmarks proposed so far: community dynamics. As time goes by network communities rise, fall and may interact with each other generating merges and splits. Indeed, during the last decade dynamic community discovery has become a very active research field: in order to provide a coherent environment to test novel algorithms aimed at identifying mutable network partitions we introduce RDYN, an approach able to generates dynamic networks along with time-dependent ground-truth partitions having tunable quality.Source: JOURNAL OF COMPLEX NETWORKS (ONLINE), vol. 5 (issue 6), pp. 893-912
DOI: 10.1093/comnet/cnx016
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
academic.oup.com | CNR IRIS | ISTI Repository | Journal of Complex Networks | CNR IRIS | CNR IRIS
2017
Journal article
Open Access
Tiles: an online algorithm for community discovery in dynamic social networks
Rossetti G, Pappalardo L, Pedreschi D, Giannotti F
Community discovery has emerged during the last decade as one of the most challenging problems in social network analysis. Many algorithms have been proposed to find communities on static networks, i.e. networks which do not change in time. However, social networks are dynamic realities (e.g. call graphs, online social networks): in such scenarios static community discovery fails to identify a partition of the graph that is semantically consistent with the temporal information expressed by the data. In this work we propose Tiles, an algorithm that extracts overlapping communities and tracks their evolution in time following an online iterative procedure. Our algorithm operates following a domino effect strategy, dynamically recomputing nodes community memberships whenever a new interaction takes place. We compare Tiles with state-of-the-art community detection algorithms on both synthetic and real world networks having annotated community structure: our experiments show that the proposed approach is able to guarantee lower execution times and better correspondence with the ground truth communities than its competitors. Moreover, we illustrate the specifics of the proposed approach by discussing the properties of identified communities it is able to identify.Source: MACHINE LEARNING, vol. 106 (issue 8), pp. 1213-1241
DOI: 10.1007/s10994-016-5582-8
Project(s): CIMPLEX, SoBigData
Metrics:
Rossetti G, Pappalardo L, Pedreschi D, Giannotti F
Community discovery has emerged during the last decade as one of the most challenging problems in social network analysis. Many algorithms have been proposed to find communities on static networks, i.e. networks which do not change in time. However, social networks are dynamic realities (e.g. call graphs, online social networks): in such scenarios static community discovery fails to identify a partition of the graph that is semantically consistent with the temporal information expressed by the data. In this work we propose Tiles, an algorithm that extracts overlapping communities and tracks their evolution in time following an online iterative procedure. Our algorithm operates following a domino effect strategy, dynamically recomputing nodes community memberships whenever a new interaction takes place. We compare Tiles with state-of-the-art community detection algorithms on both synthetic and real world networks having annotated community structure: our experiments show that the proposed approach is able to guarantee lower execution times and better correspondence with the ground truth communities than its competitors. Moreover, we illustrate the specifics of the proposed approach by discussing the properties of identified communities it is able to identify.Source: MACHINE LEARNING, vol. 106 (issue 8), pp. 1213-1241
DOI: 10.1007/s10994-016-5582-8
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
Machine Learning | CNR IRIS | link.springer.com | Machine Learning | ISTI Repository | CNR IRIS
2017
Conference article
Open Access
Market basket prediction using user-centric temporal annotated recurring sequences
Guidotti R, Rossetti G, Pappalardo L, Giannotti F, Pedreschi D
Nowadays, a hot challenge for supermarket chains is to offer personalized services to their customers. Market basket prediction, i.e., supplying the customer a shopping list for the next purchase according to her current needs, is one of these services. Current approaches are not capable of capturing at the same time the different factors influencing the customer's decision process: co-occurrence, sequentuality, periodicity and recurrency of the purchased items. To this aim, we define a pattern named Temporal Annotated Recurring Sequence (TARS). We define the method to extract TARS and develop a predictor for next basket named TBP (TARS Based Predictor) that, on top of TARS, is able to understand the level of the customer's stocks and recommend the set of most necessary items. A deep experimentation shows that TARS can explain the customers' purchase behavior, and that TBP outperforms the state-of-the-art competitors.DOI: 10.1109/icdm.2017.111
DOI: 10.13140/rg.2.2.13033.19042
Project(s): SoBigData
Metrics:
Guidotti R, Rossetti G, Pappalardo L, Giannotti F, Pedreschi D
Nowadays, a hot challenge for supermarket chains is to offer personalized services to their customers. Market basket prediction, i.e., supplying the customer a shopping list for the next purchase according to her current needs, is one of these services. Current approaches are not capable of capturing at the same time the different factors influencing the customer's decision process: co-occurrence, sequentuality, periodicity and recurrency of the purchased items. To this aim, we define a pattern named Temporal Annotated Recurring Sequence (TARS). We define the method to extract TARS and develop a predictor for next basket named TBP (TARS Based Predictor) that, on top of TARS, is able to understand the level of the customer's stocks and recommend the set of most necessary items. A deep experimentation shows that TARS can explain the customers' purchase behavior, and that TBP outperforms the state-of-the-art competitors.DOI: 10.1109/icdm.2017.111
DOI: 10.13140/rg.2.2.13033.19042
Project(s): SoBigData
Metrics:
See at:
arxiv.org | CNR IRIS | ieeexplore.ieee.org | ISTI Repository | Archivio istituzionale della Ricerca - Scuola Normale Superiore | doi.org | ResearchGate Data | CNR IRIS | CNR IRIS
2017
Journal article
Open Access
Forecasting success via early adoptions analysis: a data-driven study
Rossetti G, Milli L, Giannotti F, Pedreschi D
Innovations are continuously launched over markets, such as new products over the retail market or new artists over the music scene. Some innovations become a success; others don't. Forecasting which innovations will succeed at the beginning of their lifecycle is hard. In this paper, we provide a data-driven, large-scale account of the existence of a special niche among early adopters, individuals that consistently tend to adopt successful innovations before they reach success: we will call them Hit-Savvy. Hit-Savvy can be discovered in very different markets and retain over time their ability to anticipate the success of innovations. As our second contribution, we devise a predictive analytical process, exploiting Hit-Savvy as signals, which achieves high accuracy in the early-stage prediction of successful innovations, far beyond the reach of state-of-the-art time series forecasting models. Indeed, our findings and predictive model can be fruitfully used to support marketing strategies and product placement.Source: PLOS ONE, vol. 12 (issue 12)
DOI: 10.1371/journal.pone.0189096
Project(s): CIMPLEX, SoBigData
Metrics:
Rossetti G, Milli L, Giannotti F, Pedreschi D
Innovations are continuously launched over markets, such as new products over the retail market or new artists over the music scene. Some innovations become a success; others don't. Forecasting which innovations will succeed at the beginning of their lifecycle is hard. In this paper, we provide a data-driven, large-scale account of the existence of a special niche among early adopters, individuals that consistently tend to adopt successful innovations before they reach success: we will call them Hit-Savvy. Hit-Savvy can be discovered in very different markets and retain over time their ability to anticipate the success of innovations. As our second contribution, we devise a predictive analytical process, exploiting Hit-Savvy as signals, which achieves high accuracy in the early-stage prediction of successful innovations, far beyond the reach of state-of-the-art time series forecasting models. Indeed, our findings and predictive model can be fruitfully used to support marketing strategies and product placement.Source: PLOS ONE, vol. 12 (issue 12)
DOI: 10.1371/journal.pone.0189096
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
PLoS ONE | PLoS ONE | PLoS ONE | CNR IRIS | PLoS ONE | journals.plos.org | ISTI Repository | CNR IRIS
2017
Conference article
Open Access
Information diffusion in complex networks: The active/passive conundrum
Milli L, Rossetti G, Pedreschi D, Giannotti F
Ideas, information, viruses: all of them, with their mechanisms, can spread over the complex social tissues described by our interpersonal relations. Classical spreading models can agnostically from the object of which they simulate the diffusion, thus considering spreading of virus, ideas and innovations alike. Indeed, such simplification makes easier to define a standard set of tools that can be applied to heterogeneous contexts; however, it can also lead to biased, partial, simulation outcomes. In this work we discuss the concepts of active and passive diffusion: moving from analysis of a well-known passive model, the Threshold one, we introduce two novel approaches whose aim is to provide active and mixed schemas applicable in the context of innovations/ideas diffusion simulation. Our data-driven analysis shows how, in such context, the adoption of exclusively passive/active models leads to conflicting results, thus highlighting the need of mixed approaches.Source: STUDIES IN COMPUTATIONAL INTELLIGENCE (PRINT), vol. 689, pp. 305-313
DOI: 10.1007/978-3-319-72150-7_25
Project(s): CIMPLEX, SoBigData
Metrics:
Milli L, Rossetti G, Pedreschi D, Giannotti F
Ideas, information, viruses: all of them, with their mechanisms, can spread over the complex social tissues described by our interpersonal relations. Classical spreading models can agnostically from the object of which they simulate the diffusion, thus considering spreading of virus, ideas and innovations alike. Indeed, such simplification makes easier to define a standard set of tools that can be applied to heterogeneous contexts; however, it can also lead to biased, partial, simulation outcomes. In this work we discuss the concepts of active and passive diffusion: moving from analysis of a well-known passive model, the Threshold one, we introduce two novel approaches whose aim is to provide active and mixed schemas applicable in the context of innovations/ideas diffusion simulation. Our data-driven analysis shows how, in such context, the adoption of exclusively passive/active models leads to conflicting results, thus highlighting the need of mixed approaches.Source: STUDIES IN COMPUTATIONAL INTELLIGENCE (PRINT), vol. 689, pp. 305-313
DOI: 10.1007/978-3-319-72150-7_25
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
media.springer.com | Studies in Computational Intelligence | CNR IRIS | CNR IRIS | link.springer.com | Archivio istituzionale della Ricerca - Scuola Normale Superiore
2017
Journal article
Open Access
Node-Centric Community Discovery: from Static to Dynamic Social Network Analysis
Rossetti G, Pedreschi D, Giannotti F
Nowadays, online social networks represent privileged playgrounds that enable researchers to study, char- acterize and understand complex human behaviors. Social Network Analysis, commonly known as SNA, is the multidisciplinary field of research under which researchers of different backgrounds perform their studies: one of the hottest topics in such diversified context is indeed Community Discovery. Clustering individuals, whose relations are described by a networked structure, into homogeneous communities is a complex task required by several analytical processes. Moreover, due to the user-centric and dynamic na- ture of online social services, during the last decades, particular emphasis was dedicated to the definition of node-centric, overlapping and evolutive Community Discovery methodologies. In this paper we provide a comprehensive and concise review of the main results, both algorithmic and analytical, we obtained in this field. Moreover, to better underline the rationale behind our research activity on Community Discovery, in this work we provide a synthetic review of the relevant literature, discussing not only methodological results but also analytical ones.Source: ONLINE SOCIAL NETWORKS AND MEDIA, vol. 3-4, pp. 32-48
DOI: 10.1016/j.osnem.2017.10.003
Project(s): CIMPLEX, SoBigData
Metrics:
Rossetti G, Pedreschi D, Giannotti F
Nowadays, online social networks represent privileged playgrounds that enable researchers to study, char- acterize and understand complex human behaviors. Social Network Analysis, commonly known as SNA, is the multidisciplinary field of research under which researchers of different backgrounds perform their studies: one of the hottest topics in such diversified context is indeed Community Discovery. Clustering individuals, whose relations are described by a networked structure, into homogeneous communities is a complex task required by several analytical processes. Moreover, due to the user-centric and dynamic na- ture of online social services, during the last decades, particular emphasis was dedicated to the definition of node-centric, overlapping and evolutive Community Discovery methodologies. In this paper we provide a comprehensive and concise review of the main results, both algorithmic and analytical, we obtained in this field. Moreover, to better underline the rationale behind our research activity on Community Discovery, in this work we provide a synthetic review of the relevant literature, discussing not only methodological results but also analytical ones.Source: ONLINE SOCIAL NETWORKS AND MEDIA, vol. 3-4, pp. 32-48
DOI: 10.1016/j.osnem.2017.10.003
Project(s): CIMPLEX
, SoBigData Metrics:
See at:
Archivio istituzionale della Ricerca - Scuola Normale Superiore | Online Social Networks and Media | CNR IRIS | CNR IRIS | www.sciencedirect.com
2017
Conference article
Restricted
Dynamic Community Analysis in Decentralized Online Social Networks
Guidi B, Michienzi A, Rossetti G
Community structure is one of the most studied features of Online Social Networks (OSNs). Community detection guarantees sev- eral advantages for both centralized and decentralized social networks. Decentralized Online Social Networks (DOSNs) have been proposed to provide more control over private data. One of the main challenge in DOSNs concerns the availability of social data and communities can be exploited to guarantee a more efficient solution about the data availabil- ity problem. The detection of communities and the management of their evolution represents a hard process, especially in highly dynamic social networks, such as DOSNs, where the online/offline status of user changes very frequently. In this paper, we focus our attention on a preliminary analysis of dynamic community detection in DOSNs by studying a real Facebook dataset to evaluate how frequent the communities change over time and which events are more frequent. The results prove that the so- cial graph has a high instability and distributed solutions to manage the dynamism are needed.DOI: 10.1007/978-3-319-75178-8_42
Metrics:
Guidi B, Michienzi A, Rossetti G
Community structure is one of the most studied features of Online Social Networks (OSNs). Community detection guarantees sev- eral advantages for both centralized and decentralized social networks. Decentralized Online Social Networks (DOSNs) have been proposed to provide more control over private data. One of the main challenge in DOSNs concerns the availability of social data and communities can be exploited to guarantee a more efficient solution about the data availabil- ity problem. The detection of communities and the management of their evolution represents a hard process, especially in highly dynamic social networks, such as DOSNs, where the online/offline status of user changes very frequently. In this paper, we focus our attention on a preliminary analysis of dynamic community detection in DOSNs by studying a real Facebook dataset to evaluate how frequent the communities change over time and which events are more frequent. The results prove that the so- cial graph has a high instability and distributed solutions to manage the dynamism are needed.DOI: 10.1007/978-3-319-75178-8_42
Metrics:
See at:
doi.org | CNR IRIS | CNR IRIS | link.springer.com