Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntroducing Graph Cumulants: What is the Variance of Your Social Network?
59
0
0.0
(
0
)
Added by
Gecia Bravo-Hermsdorff
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In an increasingly interconnected world, understanding and summarizing the structure of these networks becomes increasingly relevant. However, this task is nontrivial; proposed summary statistics are as diverse as the networks they describe, and a standardized hierarchy has not yet been established. In contrast, vector-valued random variables admit such a description in terms of their cumulants (e.g., mean, (co)variance, skew, kurtosis). Here, we introduce the natural analogue of cumulants for networks, building a hierarchical description based on correlations between an increasing number of connections, seamlessly incorporating additional information, such as directed edges, node attributes, and edge weights. These graph cumulants provide a principled and unifying framework for quantifying the propensity of a network to display any substructure of interest (such as cliques to measure clustering). Moreover, they give rise to a natural hierarchical family of maximum entropy models for networks (i.e., ERGMs) that do not suffer from the degeneracy problem, a common practical pitfall of other ERGMs.
rate research
Read More
We quantify a social organizations potentiality, that is its ability to attain different configurations. The organization is represented as a network in which nodes correspond to individuals and (multi-)edges to their multiple interactions. Attainable configurations are treated as realizations from a network ensemble. To encode interaction preferences between individuals, we choose the generalized hypergeometric ensemble of random graphs, which is described by a closed-form probability distribution. From this distribution we calculate Shannon entropy as a measure of potentiality. This allows us to compare different organizations as well different stages in the development of a given organization. The feasibility of the approach is demonstrated using data from 3 empirical and 2 synthetic systems.
The proliferation of IoT devices in smart homes, hospitals, and enterprise networks is widespread and continuing to increase in a superlinear manner. With this unprecedented growth, how can one assess the security of an IoT network holistically? In this article, we explore two dimensions of security assessment, using vulnerability information of IoT devices and their underlying components ($textit{compositional security scores}$) and SIEM logs captured from the communications and operations of such devices in a network ($textit{dynamic activity metrics}$) to propose the notion of an $textit{attack circuit}$. These measures are used to evaluate the security of IoT devices and the overall IoT network, demonstrating the effectiveness of attack circuits as practical tools for computing security metrics (exploitability, impact, and risk to confidentiality, integrity, and availability) of heterogeneous networks. We propose methods for generating attack circuits with input/output pairs constructed from CVEs using natural language processing (NLP) and with weights computed using standard security scoring procedures, as well as efficient optimization methods for evaluating attack circuits. Our system provides insight into possible attack paths an adversary may utilize based on their exploitability, impact, or overall risk. We have performed experiments on IoT networks to demonstrate the efficacy of the proposed techniques.
Collaborative Filtering (CF) is one of the most successful approaches for recommender systems. With the emergence of online social networks, social recommendation has become a popular research direction. Most of these social recommendation models utilized each users local neighbors preferences to alleviate the data sparsity issue in CF. However, they only considered the local neighbors of each user and neglected the process that users preferences are influenced as information diffuses in the social network. Recently, Graph Convolutional Networks~(GCN) have shown promising results by modeling the information diffusion process in graphs that leverage both graph structure and node feature information. To this end, in this paper, we propose an effective graph convolutional neural network based model for social recommendation. Based on a classical CF model, the key idea of our proposed model is that we borrow the strengths of GCNs to capture how users preferences are influenced by the social diffusion process in social networks. The diffusion of users preferences is built on a layer-wise diffusion manner, with the initial user embedding as a function of the current users features and a free base user latent vector that is not contained in the user feature. Similarly, each items latent vector is also a combination of the items free latent vector, as well as its feature representation. Furthermore, we show that our proposed model is flexible when user and item features are not available. Finally, extensive experimental results on two real-world datasets clearly show the effectiveness of our proposed model.
On-line social networks, such as in Facebook and Twitter, are often studied from the perspective of friendship ties between agents in the network. Adversarial ties, however, also play an important role in the structure and function of social networks, but are often hidden. Underlying generative mechanisms of social networks are predicted by structural balance theory, which postulates that triads of agents, prefer to be transitive, where friends of friends are more likely friends, or anti-transitive, where adversaries of adversaries become friends. The previously proposed Iterated Local Transitivity (ILT) and Iterated Local Anti-Transitivity (ILAT) models incorporated transitivity and anti-transitivity, respectively, as evolutionary mechanisms. These models resulted in graphs with many observable properties of social networks, such as low diameter, high clustering, and densification. We propose a new, generative model, referred to as the Iterated Local Model (ILM) for social networks synthesizing both transitive and anti-transitive triads over time. In ILM, we are given a countably infinite binary sequence as input, and that sequence determines whether we apply a transitive or an anti-transitive step. The resulting model exhibits many properties of complex networks observed in the ILT and ILAT models. In particular, for any input binary sequence, we show that asymptotically the model generates finite graphs that densify, have clustering coefficient bounded away from 0, have diameter at most 3, and exhibit bad spectral expansion. We also give a thorough analysis of the chromatic number, domination number, Hamiltonicity, and isomorphism types of induced subgraphs of ILM graphs.
The Linked Data Benchmark Councils Social Network Benchmark (LDBC SNB) is an effort intended to test various functionalities of systems used for graph-like data management. For this, LDBC SNB uses the recognizable scenario of operating a social network, characterized by its graph-shaped data. LDBC SNB consists of two workloads that focus on different functionalities: the Interactive workload (interactive transactional queries) and the Business Intelligence workload (analytical queries). This document contains the definition of the Interactive Workload and the first draft of the Business Intelligence Workload. This includes a detailed explanation of the data used in the LDBC SNB benchmark, a detailed description for all queries, and instructions on how to generate the data and run the benchmark with the provided software.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
