Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the relationship between Gaussian stochastic blockmodels and label propagation algorithms
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The problem of community detection receives great attention in recent years. Many methods have been proposed to discover communities in networks. In this paper, we propose a Gaussian stochastic blockmodel that uses Gaussian distributions to fit weight of edges in networks for non-overlapping community detection. The maximum likelihood estimation of this model has the same objective function as general label propagation with node preference. The node preference of a specific vertex turns out to be a value proportional to the intra-community eigenvector centrality (the corresponding entry in principal eigenvector of the adjacency matrix of the subgraph inside that vertexs community) under maximum likelihood estimation. Additionally, the maximum likelihood estimation of a constrained version of our model is highly related to another extension of label propagation algorithm, namely, the label propagation algorithm under constraint. Experiments show that the proposed Gaussian stochastic blockmodel performs well on various benchmark networks.
rate research
Read More
In 2020, countries affected by the COVID-19 pandemic implemented various non-pharmaceutical interventions to contrast the spread of the virus and its impact on their healthcare systems and economies. Using Italian data at different geographic scales, we investigate the relationship between human mobility, which subsumes many facets of the populations response to the changing situation, and the spread of COVID-19. Leveraging mobile phone data from February through September 2020, we find a striking relationship between the decrease in mobility flows and the net reproduction number. We find that the time needed to switch off mobility and bring the net reproduction number below the critical threshold of 1 is about one week. Moreover, we observe a strong relationship between the number of days spent above such threshold before the lockdown-induced drop in mobility flows and the total number of infections per 100k inhabitants. Estimating the statistical effect of mobility flows on the net reproduction number over time, we document a 2-week lag positive association, strong in March and April, and weaker but still significant in June. Our study demonstrates the value of big mobility data to monitor the epidemic and inform control interventions during its unfolding.
Peoples interests and peoples social relationships are intuitively connected, but understanding their interplay and whether they can help predict each other has remained an open question. We examine the interface of two decisive structures forming the backbone of online social media: the graph structure of social networks - who connects with whom - and the set structure of topical affiliations - who is interested in what. In studying this interface, we identify key relationships whereby each of these structures can be understood in terms of the other. The context for our analysis is Twitter, a complex social network of both follower relationships and communication relationships. On Twitter, hashtags are used to label conversation topics, and we examine hashtag usage alongside these social structures. We find that the hashtags that users adopt can predict their social relationships, and also that the social relationships between the initial adopters of a hashtag can predict the future popularity of that hashtag. By studying weighted social relationships, we observe that while strong reciprocated ties are the easiest to predict from hashtag structure, they are also much less useful than weak directed ties for predicting hashtag popularity. Importantly, we show that computationally simple structural determinants can provide remarkable performance in both tasks. While our analyses focus on Twitter, we view our findings as broadly applicable to topical affiliations and social relationships in a host of diverse contexts, including the movies people watch, the brands people like, or the locations people frequent.
Identifying communities has always been a fundamental task in analysis of complex networks. Many methods have been devised over the last decade for detection of communities. Amongst them, the label propagation algorithm brings great scalability together with high accuracy. However, it has one major flaw; when the community structure in the network is not clear enough, it will assign every node the same label, thus detecting the whole graph as one giant community. We have addressed this issue by setting a capacity for communities, starting from a small value and gradually increasing it over time. Preliminary results show that not only our extension improves the detection capability of classic label propagation algorithm when communities are not clearly detectable, but also improves the overall quality of the identified clusters in complex networks with a clear community structure.
This article presents a study that compares detected structural communities in a coauthorship network to the socioacademic characteristics of the scholars that compose the network. The coauthorship network was created from the bibliographic record of a multi-institution, interdisciplinary research group focused on the study of sensor networks and wireless communication. Four different community detection algorithms were employed to assign a structural community to each scholar in the network: leading eigenvector, walktrap, edge betweenness and spinglass. Socioacademic characteristics were gathered from the scholars and include such information as their academic department, academic affiliation, country of origin, and academic position. A Pearsons $chi^2$ test, with a simulated Monte Carlo, revealed that structural communities best represent groupings of individuals working in the same academic department and at the same institution. A generalization of this result suggests that, even in interdisciplinary, multi-institutional research groups, coauthorship is primarily driven by departmental and institutional affiliation.
Community detection is a fundamental and important problem in network science, as community structures often reveal both topological and functional relationships between different components of the complex system. In this paper, we first propose a gradient descent framework of modularity optimization called vector-label propagation algorithm (VLPA), where a node is associated with a vector of continuous community labels instead of one label. Retaining weak structural information in vector-label, VLPA outperforms some well-known community detection methods, and particularly improves the performance in networks with weak community structures. Further, we incorporate stochastic gradient strategies into VLPA to avoid stuck in the local optima, leading to the stochastic vector-label propagation algorithm (sVLPA). We show that sVLPA performs better than Louvain Method, a widely used community detection algorithm, on both artificial benchmarks and real-world networks. Our theoretical scheme based on vector-label propagation can be directly applied to high-dimensional networks where each node has multiple features, and can also be used for optimizing other partition measures such as modularity with resolution parameters.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
