اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAxiomatic Ranking of Network Role Similarity
127
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A key task in social network and other complex network analysis is role analysis: describing and categorizing nodes according to how they interact with other nodes. Two nodes have the same role if they interact with equivalent sets of neighbors. The most fundamental role equivalence is automorphic equivalence. Unfortunately, the fastest algorithms known for graph automorphism are nonpolynomial. Moreover, since exact equivalence may be rare, a more meaningful task is to measure the role similarity between any two nodes. This task is closely related to the structural or link-based similarity problem that SimRank attempts to solve. However, SimRank and most of its offshoots are not sufficient because they do not fully recognize automorphically or structurally equivalent nodes. In this paper we tackle two problems. First, what are the necessary properties for a role similarity measure or metric? Second, how can we derive a role similarity measure satisfying these properties? For the first problem, we justify several axiomatic properties necessary for a role similarity measure or metric: range, maximal similarity, automorphic equivalence, transitive similarity, and the triangle inequality. For the second problem, we present RoleSim, a new similarity metric with a simple iterative computational method. We rigorously prove that RoleSim satisfies all the axiomatic properties. We also introduce an iceberg RoleSim algorithm which can guarantee to discover all pairs with RoleSim score no less than a user-defined threshold $theta$ without computing the RoleSim for every pair. We demonstrate the superior interpretative power of RoleSim on both both synthetic and real datasets.
قيم البحث
اقرأ أيضاً
We deal with the problem of automatically generating social networks by analyzing and assessing smartphone usage and interaction data. We start by assigning weights to the different types of interactions such as messaging, email, phone calls, chat an
d physical proximity. Next, we propose a ranking algorithm which recognizes the pattern of interaction taking into account the changes in the collected data over time. Both algorithms are based on recent findings from social network research.
Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partitio
n of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of random graphs, the Ranked Stochastic Block Model. We find that agony may fail to identify hierarchies when the structure is not strong enough and the size of the classes is small with respect to the whole network. We analytically characterise the resolution threshold and we show that an iterated version of agony can partly overcome this resolution limit.
Information is a valuable asset for agents in socio-economic systems, a significant part of the information being entailed into the very network of connections between agents. The different interlinkages patterns that agents establish may, in fact, l
ead to asymmetries in the knowledge of the network structure; since this entails a different ability of quantifying relevant systemic properties (e.g. the risk of financial contagion in a network of liabilities), agents capable of providing a better estimate of (otherwise) unaccessible network properties, ultimately have a competitive advantage. In this paper, we address for the first time the issue of quantifying the information asymmetry arising from the network topology. To this aim, we define a novel index - InfoRank - intended to measure the quality of the information possessed by each node, computing the Shannon entropy of the ensemble conditioned on the node-specific information. Further, we test the performance of our novel ranking procedure in terms of the reconstruction accuracy of the (unaccessible) network structure and show that it outperforms other popular centrality measures in identifying the most informative nodes. Finally, we discuss the socio-economic implications of network information asymmetry.
Over the years, quantifying the similarity of nodes has been a hot topic in complex networks, yet little has been known about the distributions of node-similarity. In this paper, we consider a typical measure of node-similarity called the common neig
hbor based similarity (CNS). By means of the generating function, we propose a general framework for calculating the CNS distributions of node sets in various complex networks. In particular, we show that for the Erd{o}s-R{e}nyi (ER) random network, the CNS distribution of node sets of any particular size obeys the Poisson law. We also connect the node-similarity distribution to the link prediction problem. We found that the performance of link prediction depends solely on the CNS distributions of the connected and unconnected node pairs in the network. Furthermore, we derive theoretical solutions of two key evaluation metrics in link prediction: i) precision and ii) area under the receiver operating characteristic curve (AUC). We show that for any link prediction method, if the similarity distributions of the connected and unconnected node pairs are identical, the AUC will be $0.5$. The theoretical solutions are elegant alternatives of the traditional experimental evaluation methods with nevertheless much lower computational cost.
We study social networks and focus on covert (also known as hidden) networks, such as terrorist or criminal networks. Their structures, memberships and activities are illegal. Thus, data about covert networks is often incomplete and partially incorre
ct, making interpreting structures and activities of such networks challenging. For legal reasons, real data about active covert networks is inaccessible to researchers. To address these challenges, we introduce here a network generator for synthetic networks that are statistically similar to a real network but void of personal information about its members. The generator uses statistical data about a real or imagined covert organization network. It generates randomized instances of the Stochastic Block model of the network groups but preserves this network organizational structure. The direct use of such anonymized networks is for training on them the research and analytical tools for finding structure and dynamics of covert networks. Since these synthetic networks differ in their sets of edges and communities, they can be used as a new source for network analytics. First, they provide alternative interpretations of the data about the original network. The distribution of probabilities for these alternative interpretations enables new network analytics. The analysts can find community structures which are frequent, therefore stable under perturbations. They may also analyze how the stability changes with the strength of perturbation. For covert networks, the analysts can quantify statistically expected outcomes of interdiction. This kind of analytics applies to all complex network in which the data are incomplete or partially incorrect.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
