Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2012
Report
Open Access
A classification for community discovery methods in complex networks
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges,multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: ISTI Technical reports, pp.512–546, 2012
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
Coscia M., Giannotti F., Pedreschi D.
Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a 'user manual' for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges,multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.Source: ISTI Technical reports, pp.512–546, 2012
DOI: 10.1002/sam.10133
DOI: 10.48550/arxiv.1206.3552
Metrics:
See at:
arXiv.org e-Print Archive 
| Statistical Analysis and Data Mining The ASA Data Science Journal | ISTI Repository | Statistical Analysis and Data Mining The ASA Data Science Journal 
| doi.org | CNR ExploRA
2012
Journal article
Restricted
Discovering the geographical borders of human mobility
Rinzivillo S., Mainardi S., Pezzoni F., Coscia M., Pedreschi D., Giannotti F.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human behavior and interactions. Broad, extensive, and multidisciplinary research has been devoted to the extraction of non-trivial knowledge from this novel form of data. We propose a general method to determine the influence of social and mobility behavior over a specific geographical area in order to evaluate to what extent the current administrative borders represent the real basin of human movement. We build a network representation of human movement starting with vehicle GPS tracks and extract relevant clusters, which are then mapped back onto the territory, finding a good match with the existing administrative borders. The novelty of our approach is the focus on a detailed spatial resolution, we map emerging borders in terms of individual municipalities, rather than macro regional or national areas. We present a series of experiments to illustrate and evaluate the effectiveness of our approach.Source: KI. Künstliche Intelligenz (Oldenbourg) 26 (2012): 253–260. doi:10.1007/s13218-012-0181-8
DOI: 10.1007/s13218-012-0181-8
Project(s): DATA SIM
Metrics:
Rinzivillo S., Mainardi S., Pezzoni F., Coscia M., Pedreschi D., Giannotti F.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human behavior and interactions. Broad, extensive, and multidisciplinary research has been devoted to the extraction of non-trivial knowledge from this novel form of data. We propose a general method to determine the influence of social and mobility behavior over a specific geographical area in order to evaluate to what extent the current administrative borders represent the real basin of human movement. We build a network representation of human movement starting with vehicle GPS tracks and extract relevant clusters, which are then mapped back onto the territory, finding a good match with the existing administrative borders. The novelty of our approach is the focus on a detailed spatial resolution, we map emerging borders in terms of individual municipalities, rather than macro regional or national areas. We present a series of experiments to illustrate and evaluate the effectiveness of our approach.Source: KI. Künstliche Intelligenz (Oldenbourg) 26 (2012): 253–260. doi:10.1007/s13218-012-0181-8
DOI: 10.1007/s13218-012-0181-8
Project(s): DATA SIM
Metrics:
See at:
KI - Künstliche Intelligenz | link.springer.com | CNR ExploRA
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
Classifying trust/distrust relationships in online social networks
Bachi G., Coscia M., Monreale A., Giannotti F.
Online social networks are increasingly being used as places where communities gather to exchange information, form opinions, collaborate in response to events. An aspect of this information exchange is how to determine if a source of social information can be trusted or not. Data mining literature addresses this problem. However, if usually employs social bal- ance theories, by looking at small structures in complex networks known as triangles. This has proven effective in some cases, but it under performs in the lack of context information about the relation and in more complex interactive structures. In this paper we address the problem of creating a framework for the trust inference, able to infer the trust/distrust relationships in those relational environments that cannot be described by using the classical social balance theory. We do so by decomposing a trust network in its ego network components and mining on this ego network set the trust relationships, extending a well known graph mining algorithm. We test our framework on three public datasets describing trust relationships in the real world (from the social media Epinions, Slashdot and Wikipedia) and confronting our results with the trust inference state of the art, showing better performances where the social balance theory fails.Source: International Conference on Privacy, Security, Risk and Trust 2012 and 2012, pp. 552–557, Amsterdam, 3-5 September 2012
DOI: 10.1109/socialcom-passat.2012.115
Metrics:
Bachi G., Coscia M., Monreale A., Giannotti F.
Online social networks are increasingly being used as places where communities gather to exchange information, form opinions, collaborate in response to events. An aspect of this information exchange is how to determine if a source of social information can be trusted or not. Data mining literature addresses this problem. However, if usually employs social bal- ance theories, by looking at small structures in complex networks known as triangles. This has proven effective in some cases, but it under performs in the lack of context information about the relation and in more complex interactive structures. In this paper we address the problem of creating a framework for the trust inference, able to infer the trust/distrust relationships in those relational environments that cannot be described by using the classical social balance theory. We do so by decomposing a trust network in its ego network components and mining on this ego network set the trust relationships, extending a well known graph mining algorithm. We test our framework on three public datasets describing trust relationships in the real world (from the social media Epinions, Slashdot and Wikipedia) and confronting our results with the trust inference state of the art, showing better performances where the social balance theory fails.Source: International Conference on Privacy, Security, Risk and Trust 2012 and 2012, pp. 552–557, Amsterdam, 3-5 September 2012
DOI: 10.1109/socialcom-passat.2012.115
Metrics:
See at:
www.michelecoscia.com | doi.org | ieeexplore.ieee.org | CNR ExploRA
2012
Conference article
Restricted
Optimal spatial resolution for the analysis of human mobility
Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human be- haviors and interactions. This data availability leads to challenges in the knowledge discovery community. Several different analyses have been performed on the traces of human trajectories, such as understanding the real borders of human mobility or mining social interactions derived from mobility and viceversa. However, the data quality of the digital traces of human mobility has a dramatic impact over the knowledge that it is possible to mine, and this issue has not been thoroughly tackled so far in literature. In this paper, we mine and analyze with complex network techniques a large dataset of human trajectories, a GPS dataset from more than 150k vehicles in Italy. We build a multiresolution grid and we map the trajectories with several complex networks, by connecting the different areas of our region of interest. Then we analyze the structural properties of these networks and the quality of the borders it is possible to infer from them. The result is a significant advancement in our understanding of the data transformation process that is needed to connect mobility with social network analysis and mining.Source: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 248–252, Instanbul, Turkey, 26-29 August 2012
Coscia M., Rinzivillo S., Giannotti F., Pedreschi D.
The availability of massive network and mobility data from diverse domains has fostered the analysis of human be- haviors and interactions. This data availability leads to challenges in the knowledge discovery community. Several different analyses have been performed on the traces of human trajectories, such as understanding the real borders of human mobility or mining social interactions derived from mobility and viceversa. However, the data quality of the digital traces of human mobility has a dramatic impact over the knowledge that it is possible to mine, and this issue has not been thoroughly tackled so far in literature. In this paper, we mine and analyze with complex network techniques a large dataset of human trajectories, a GPS dataset from more than 150k vehicles in Italy. We build a multiresolution grid and we map the trajectories with several complex networks, by connecting the different areas of our region of interest. Then we analyze the structural properties of these networks and the quality of the borders it is possible to infer from them. The result is a significant advancement in our understanding of the data transformation process that is needed to connect mobility with social network analysis and mining.Source: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 248–252, Instanbul, Turkey, 26-29 August 2012
See at:
ieeexplore.ieee.org | CNR ExploRA
2012
Conference article
Restricted
Knowing where and how criminal organizations operate using web content
Coscia M., Rios V.
We develop a framework that uses Web content to obtain quantitative information about a phenomenon that would otherwise require the operation of large scale, expensive intelligence exercises. Exploiting indexed reliable sources such as online newspapers and blogs, we use unambiguous query terms to characterize a complex evolving phenomena and solve a security policy problem: identifying the areas of operation and modus operandi of criminal organizations, in particular, Mexican drug tracking organizations over the last two decades. We validate our methodology by comparing information that is known with certainty with the one we extracted using our framework.We show that our framework is able to use information available on the web to eciently extract implicit knowledge about criminal organizations. In the scenario of Mexican drug tracking, our ndings provide evidence that criminal organizations are more strategic and operate in more dierentiated ways than current academic literature thought.Source: The 21st ACM International Conference on Information and Knowledge Management, pp. 1412–1421, Maui, Hawaii, USA, October 29-November 2 2012
DOI: 10.1145/2396761.2398446
Metrics:
Coscia M., Rios V.
We develop a framework that uses Web content to obtain quantitative information about a phenomenon that would otherwise require the operation of large scale, expensive intelligence exercises. Exploiting indexed reliable sources such as online newspapers and blogs, we use unambiguous query terms to characterize a complex evolving phenomena and solve a security policy problem: identifying the areas of operation and modus operandi of criminal organizations, in particular, Mexican drug tracking organizations over the last two decades. We validate our methodology by comparing information that is known with certainty with the one we extracted using our framework.We show that our framework is able to use information available on the web to eciently extract implicit knowledge about criminal organizations. In the scenario of Mexican drug tracking, our ndings provide evidence that criminal organizations are more strategic and operate in more dierentiated ways than current academic literature thought.Source: The 21st ACM International Conference on Information and Knowledge Management, pp. 1412–1421, Maui, Hawaii, USA, October 29-November 2 2012
DOI: 10.1145/2396761.2398446
Metrics:
See at:
dl.acm.org | doi.org | CNR ExploRA