دانلود رایگان مقاله توپولوژی مشترک و نمونه برداری ویژگی و نسل نمودارهای شبکه های اجتماعی

abstract

Graph sampling refers to the process of deriving a small subset of nodes from a possibly huge graph in order to estimate properties of the whole graph from examining the sample. Whereas topological properties can already be obtained accurately by sampling, current approaches do not take possibly hidden dependencies between node topology and attributes into account. Especially in the context of online social networks, node attributes are of importance as they correspond to properties of the social network’s users. Therefore, existing sampling algorithms can be extended to attribute sampling, but still lack the capturing of structural properties. Analyzing topology (e.g., node degree and clustering coefficient) and attribute properties (e.g., age and location) jointly can provide valuable insights into the social network and allows for a better understanding of social processes. As major contribution, this work proposes a novel sampling algorithm which provides unbiased and reliable estimates of joint topological and attribute based graph properties in a resource effi- cient fashion. Furthermore, the obtained samples allow for the generation of synthetic graphs, which show high similarity to the original graph with respect to topology and attributes. The proposed sampling and generation algorithms are evaluated on real world social network graphs, for which they demonstrate to be effective.

6. Discussion

In this work, a practical methodology for efficiently estimating topological and attribute related properties of graphs with node attributes was developed. As this estimation relies on a node sample whose size is significantly smaller than that of the input graph’s node set, the developed sampling algorithm can be used in order to estimate properties of huge real world graphs like online social networks. This property makes it suitable for different use cases, e.g., socially aware traffic management, where attribute related graph properties need to be computed in a fast and reliable manner. Furthermore, a mechanism for generating synthetic graphs with node attributes was designed. In contrast to previous state-of-the-art graph generation algorithms, it does not require full knowledge of the input graph in order to replicate the graph’s key characteristics with respect to topology and node attributes. Thus, crawling a small subset of an input graph allows generating realistic graphs that can be used in the context of algorithm benchmarks or simulations. After designing and implementing both algorithms, their performance was evaluated in a test framework on several real social network graphs with attributes. The evaluation helped to quantify the influence of algorithm parameters on their performance and to find optimum values for these parameters. Comparisons indicate that the developed mechanisms are on a par with state-of-the-art algorithms when it comes to performance with respect to topological aspects.