For network scientists, it has always been an interesting problem to identify the influential nodes in a given network. The k-shell decomposition method is a widely used method which assigns a shell-index value to each node based on its influential power. The k-shell method requires the global information of the network to compute the shell-index of a node that is infeasible for large-scale real-world dynamic networks. In this work, we propose a method to estimate the shell-index of a node using its local information. We also propose hill-climbing based approach to hit the top-ranked nodes in a small number of steps. We further discuss a method to estimate the rank of a node based on the proposed estimator.
K-shell method has been widely used in literature to study different networks. used shell-index to identify clusters in PubMed scientific publications @cite_48 . To identify the clusters, a graph is created where the nodes are the publications, and there is an edge between two nodes if the distance between the locations of the corresponding researchers is less than the threshold. In the experiments, authors have taken the threshold 1 km. Based on the k-shell decomposition, authors categorized the cities into monocore and multicore. Later on, the journal impact factors are used to quantify the quality of research of each core. Results show that k-shell decomposition method can be used to identify the research hub clusters.
@cite_48
2141806644 2963004719 2091252309 2128364989
We present a generalized method for calculating the k-shell structure of weighted networks. The method takes into account both the weight and the degree of a network, in such a way that in the absence of weights we resume the shell structure obtained by the classic k-shell decomposition. In the presence of weights, we show that the method is able to partition the network in a more refined way, without the need of any arbitrary threshold on the weight values. Furthermore, by simulating spreading processes using the susceptible- infectious-recovered model in four different weighted real-world networks, we show that the weighted k-shell decomposition method ranks the nodes more accurately, by placing nodes with higher spreading potential into shells closer to the core. In addition, we demonstrate our new method on a real economic network and show that the core calculated using the weighted k-shell method is more meaningful from an economic perspective when compared with the unweighted one. The k-core decomposition is a widely studied summary statistic that describes a graph’s global connectivity structure. In this paper, we move beyond using k-core decomposition as a tool to summarize a graph and propose using k-core decomposition as a tool to model random graphs. We propose using the shell distribution vector, a way of summarizing the decomposition, as a sufficient statistic for a family of exponential random graph models. We study the properties and behavior of the model family, implement a Markov chain Monte Carlo algorithm for simulating graphs from the model, implement a direct sampler from the set of graphs with a given shell distribution, and explore the sampling distributions of some of the commonly used complementary statistics as good candidates for heuristic model fitting. These algorithms the provide first fundamental steps necessary for solving the following problems: parameter estimation in this ERGM, extending the model to its Bayesian relative, and developing a rigorous methodology for testing goodness of fit of the model and model selection. The methods are applied to a synthetic network as well as the well-known Sampson monks dataset. Identifying influential nodes in complex networks has attracted much attention because of its great theoretical significance and wide application. Existing methods consider the edges equally when designing identifying methods for the unweighted networks. In this paper, we propose an edge weighting method based on adding the degree of its two end nodes and for the constructed weighted networks, we propose a weighted k-shell decomposition method (Wks). Further investigations on the epidemic spreading process of the Susceptible–Infected–Recovered (SIR) model and Susceptible–Infected (SI) model in real complex networks verify that our method is effective for detecting the node influence. When clusters with different densities and noise lie in a spatial point set, the major obstacle to classifying these data is the determination of the thresholds for classification, which may form a series of bins for allocating each point to different clusters. Much of the previous work has adopted a model-based approach, but is either incapable of estimating the thresholds in an automatic way, or limited to only two point processes, i.e. noise and clusters with the same density. In this paper, we present a new density-based cluster method (DECODE), in which a spatial data set is presumed to consist of different point processes and clusters with different densities belong to different point processes. DECODE is based upon a reversible jump Markov Chain Monte Carlo (MCMC) strategy and divided into three steps. The first step is to map each point in the data to its mth nearest distance, which is referred to as the distance between a point and its mth nearest neighbor. In the second step, classification thresholds are determined via a reversible jump MCMC strategy. In the third step, clusters are formed by spatially connecting the points whose mth nearest distances fall into a particular bin defined by the thresholds. Four experiments, including two simulated data sets and two seismic data sets, are used to evaluate the algorithm. Results on simulated data show that our approach is capable of discovering the clusters automatically. Results on seismic data suggest that the clustered earthquakes, identified by DECODE, either imply the epicenters of forthcoming strong earthquakes or indicate the areas with the most intensive seismicity, this is consistent with the tectonic states and estimated stress distribution in the associated areas. The comparison between DECODE and other state-of-the-art methods, such as DBSCAN, OPTICS and Wavelet Cluster, illustrates the contribution of our approach: although DECODE can be computationally expensive, it is capable of identifying the number of point processes and simultaneously estimating the classification thresholds with little prior knowledge.