Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterizing and Utilizing the Interplay Between Core and Truss Decompositions
153
0
0.0
(
0
)
Added by
Penghang Liu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Finding the dense regions in a graph is an important problem in network analysis. Core decomposition and truss decomposition address this problem from two different perspectives. The former is a vertex-driven approach that assigns density indicators for vertices whereas the latter is an edge-driven technique that put density quantifiers on edges. Despite the algorithmic similarity between these two approaches, it is not clear how core and truss decompositions in a network are related. In this work, we introduce the vertex interplay (VI) and edge interplay (EI) plots to characterize the interplay between core and truss decompositions. Based on our observations, we devise CORE-TRUSSDD, an anomaly detection algorithm to identify the discrepancies between core and truss decompositions. We analyze a large and diverse set of real-world networks, and demonstrate how our approaches can be effective tools to characterize the patterns and anomalies in the networks. Through VI and EI plots, we observe distinct behaviors for graphs from different domains, and identify two anomalous behaviors driven by specific real-world structures. Our algorithm provides an efficient solution to retrieve the outliers in the networks, which correspond to the two anomalous behaviors. We believe that investigating the interplay between core and truss decompositions is important and can yield surprising insights regarding the dense subgraph structure of real-world networks.
rate research
Read More
Conformational transitions of flexible molecules, especially those driven by hydrophobic effects, tend to be hindered by desolvation barriers. For such transitions, it is thus important to characterize and understand the interplay between solvation and conformation. Using specialized molecular simulations, here we perform such a characterization for a hydrophobic polymer solvated in water. We find that an external potential, which unfavorably perturbs the polymer hydration waters, can trigger a coil-to-globule or collapse transition, and that the relative stabilities of the collapsed and extended states can be quantified by the strength of the requisite potential. Our results also provide mechanistic insights into the collapse transition, highlighting that polymer collapse proceeds through the formation of a sufficiently large non-polar cluster, and that collective water density fluctuations play an important role in stabilizing such a cluster. We also study the collapse of the hydrophobic polymer in octane, a non-polar solvent, and interestingly, we find that the mechanistic details of the transition are qualitatively similar to that in water.
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.
The organisation of a network in a maximal set of nodes having at least $k$ neighbours within the set, known as $k$-core decomposition, has been used for studying various phenomena. It has been shown that nodes in the innermost $k$-shells play a crucial role in contagion processes, emergence of consensus, and resilience of the system. It is known that the $k$-core decomposition of many empirical networks cannot be explained by the degree of each node alone, or equivalently, random graph models that preserve the degree of each node (i.e., configuration model). Here we study the $k$-core decomposition of some empirical networks as well as that of some randomised counterparts, and examine the extent to which the $k$-shell structure of the networks can be accounted for by the community structure. We find that preserving the community structure in the randomisation process is crucial for generating networks whose $k$-core decomposition is close to the empirical one. We also highlight the existence, in some networks, of a concentration of the nodes in the innermost $k$-shells into a small number of communities.
We study network centrality based on dynamic influence propagation models in social networks. To illustrate our integrated mathematical-algorithmic approach for understanding the fundamental interplay between dynamic influence processes and static network structures, we focus on two basic centrality measures: (a) Single Node Influence (SNI) centrality, which measures each nodes significance by its influence spread; and (b) Shapley Centrality, which uses the Shapley value of the influence spread function --- formulated based on a fundamental cooperative-game-theoretical concept --- to measure the significance of nodes. We present a comprehensive comparative study of these two centrality measures. Mathematically, we present axiomatic characterizations, which precisely capture the essence of these two centrality measures and their fundamental differences. Algorithmically, we provide scalable algorithms for approximating them for a large family of social-influence instances. Empirically, we demonstrate their similarity and differences in a number of real-world social networks, as well as the efficiency of our scalable algorithms. Our results shed light on their applicability: SNI centrality is suitable for assessing individual influence in isolation while Shapley centrality assesses individuals performance in group influence settings.
We extend a recent computation of the dependence of the free energy, F, on the noncommutative scale $theta$ to theories with very different UV sensitivity. The temperature dependence of $F$ strongly suggests that a reduced number of degrees of freedom contributes to the free energy in the non-planar sector, $F_{rm np}$, at high temperature. This phenomenon seems generic, independent of the UV sensitivity, and can be traced to modes whose thermal wavelengths become smaller than the noncommutativity scale. The temperature dependence of $F_{rm np}$ can then be calculated at high temperature using classical statistical mechanics, without encountering a UV catastrophe even in large number of dimensions. This result is a telltale sign of the low number of degrees of freedom contributing to $F$ in the non-planar sector at high temperature. Such behavior is in marked contrast to what would happen in a field theory with a random set of higher derivative interactions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
