Knowledge bases of entities and relations (either constructed manually or automatically) are behind many real world search engines, including those at Yahoo!, Microsoft, and Google. Those knowledge bases can be viewed as graphs with nodes representin
g entities and edges representing (primary) relationships, and various studies have been conducted on how to leverage them to answer entity seeking queries. Meanwhile, in a complementary direction, analyses over the query logs have enabled researchers to identify entity pairs that are statistically correlated. Such entity relationships are then presented to search users through the related searches feature in modern search engines. However, entity relationships thus discovered can often be puzzling to the users because why the entities are connected is often indescribable. In this paper, we propose a novel problem called entity relationship explanation, which seeks to explain why a pair of entities are connected, and solve this challenging problem by integrating the above two complementary approaches, i.e., we leverage the knowledge base to explain the connections discovered between entity pairs. More specifically, we present REX, a system that takes a pair of entities in a given knowledge base as input and efficiently identifies a ranked list of relationship explanations. We formally define relationship explanations and analyze their desirable properties. Furthermore, we design and implement algorithms to efficiently enumerate and rank all relationship explanations based on multiple measures of interestingness. We perform extensive experiments over real web-scale data gathered from DBpedia and a commercial search engine, demonstrating the efficiency and scalability of REX. We also perform user studies to corroborate the effectiveness of explanations generated by REX.
The closed-form solution for the average distance of a deterministic network--Sierpinski network--is found. This important quantity is calculated exactly with the help of recursion relations, which are based on the self-similar network structure and
enable one to derive the precise formula analytically. The obtained rigorous solution confirms our previous numerical result, which shows that the average distance grows logarithmically with the number of network nodes. The result is at variance with that derived from random networks.
Many real systems possess accelerating statistics where the total number of edges grows faster than the network size. In this paper, we propose a simple weighted network model with accelerating growth. We derive analytical expressions for the evoluti
ons and distributions for strength, degree, and weight, which are relevant to accelerating growth. We also find that accelerating growth determines the clustering coefficient of the networks. Interestingly, the distributions for strength, degree, and weight display a transition from scale-free to exponential form when the parameter with respect to accelerating growth increases from a small to large value. All the theoretical predictions are successfully contrasted with extensive numerical simulations.
We propose a synthetical weights dynamic mechanism for weighted networks which takes into account the influences of strengths of nodes, weights of links and incoming new vertices. Strength/Weight preferential strategies are used in these weights dyna
mic mechanisms, which depict the evolving strategies of many real-world networks. We give insight analysis to the synthetical weights dynamic mechanism and study how individual weights dynamic strategies interact and cooperate with each other in the networks evolving process. Power-law distributions of strength, degree and weight, nontrivial strength-degree correlation, clustering coefficients and assortativeness are found in the model with tunable parameters representing each model. Several homogenous functionalities of these independent weights dynamic strategy are generalized and their synergy are studied.
Many real networks share three generic properties: they are scale-free, display a small-world effect, and show a power-law strength-degree correlation. In this paper, we propose a type of deterministically growing networks called Sierpinski networks,
which are induced by the famous Sierpinski fractals and constructed in a simple iterative way. We derive analytical expressions for degree distribution, strength distribution, clustering coefficient, and strength-degree correlation, which agree well with the characterizations of various real-life networks. Moreover, we show that the introduced Sierpinski networks are maximal planar graphs.
