The spatial preferential attachment (SPA) is a model for complex networks. In the SPA model, nodes are embedded in a metric space, and each node has a sphere of influence whose size increases if the node gains an in-link, and otherwise decreases with time. In this paper, we study the behaviour of the SPA model when the distribution of the nodes is non-uniform. Specifically, the space is divided into dense and sparse regions, where it is assumed that the dense regions correspond to coherent communities. We prove precise theoretical results regarding the degree of a node, the number of common neighbours, and the average out-degree in a region. Moreover, we show how these theoretically derived results about the graph properties of the model can be used to formulate a reliable estimator for the distance between certain pairs of nodes, and to estimate the density of the region containing a given node.
Efforts to extract node information through link analysis began with a heuristic quantification of entity similarity: numerical values, obtained from the graph structure, indicating the relatedness of two nodes. Early simple measures of entity similarity, such as the Jaccard coefficient @cite_6 , gave way to iterative graph theoretic measures, in which two objects are similar if they are related to similar objects, such as SimRank @cite_4 . Many such measures also incorporate co-citation, the number of common neighbours of two nodes, as proposed in the context of bibliographic research in an early paper by Small @cite_16 . @cite_17 , the authors make inferences on the social space for nodes in a social network, using Bayesian methods and maximum likelihood.
@cite_16 @cite_4 @cite_6 @cite_17
2005207065 2117831564 1555083332 2066459332
A new form of document coupling called co-citation is defined as the frequency with which two documents are cited together. The co-citation frequency of two scientific papers can be determined by comparing lists of citing documents in the Science Citation Index and counting identical entries. Networks of co-cited papers can be generated for specific scientific specialties, and an example is drawn from the literature of particle physics. Co-citation patterns are found to differ significantly from bibliographic coupling patterns, but to agree generally with patterns of direct citation. Clusters of co-cited papers provide a new way to study the specialty structure of science. They may provide a new approach to indexing and to the creation of SDI profiles. The problem of measuring "similarity" of objects arises in many applications, and many domain-specific measures have been developed, e.g., matching text across documents or computing overlap among item-sets. We propose a complementary approach, applicable in any domain with object-to-object relationships, that measures similarity of the structural context in which objects occur, based on their relationships with other objects. Effectively, we compute a measure that says "two objects are similar if they are related to similar objects:" This general similarity measure, called SimRank, is based on a simple and intuitive graph-theoretic model. For a given domain, SimRank can be combined with other domain-specific similarity measures. We suggest techniques for efficient computation of SimRank scores, and provide experimental results on two application domains showing the computational feasibility and effectiveness of our approach. This paper proposes an algorithm and data structure for fast computation of similarity based on Jaccard coefficient to retrieve images with regions similar to those of a query image. The similarity measures the degree of overlap between the regions of an image and those of another image. The key idea for fast computation of the similarity is to use the runlength description of an image for computing the number of overlapped pixels between the regions. We present an algorithm and data structure, and do experiments on 30,000 images to evaluate the performance of our algorithm. Experiments showed that the proposed algorithm is 5.49 (2.36) times faster than a naive algorithm on the average (the worst). And we theoretically gave fairly good estimates of the computation time. Network models are widely used to represent relational information among interacting units. In studies of social networks, recent emphasis has been placed on random graph models where the nodes usually represent individual social actors and the edges represent the presence of a specified relation between actors. We develop a class of models where the probability of a relation between actors depends on the positions of individuals in an unobserved “social space.” We make inference for the social space within maximum likelihood and Bayesian frameworks, and propose Markov chain Monte Carlo procedures for making inference on latent positions and the effects of observed covariates. We present analyses of three standard datasets from the social networks literature, and compare the method to an alternative stochastic blockmodeling approach. In addition to improving on model fit for these datasets, our method provides a visual and interpretable model-based spatial representation of social relationships and improv...