ترغب بنشر مسار تعليمي؟ اضغط هنا

Relay a message as far as possible with local decisions in a network

150   0   0.0 ( 0 )
 نشر من قبل Ricky Xiaofeng Chen
 تاريخ النشر 2021
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Ricky X. F. Chen




اسأل ChatGPT حول البحث

Suppose there is a message generated at a node $v$ in a network and $v$ decides to pass the message to one of the neighbors $u$, and $u$ next decides to pass the message to one of its own neighbors, and so on. How to relay the message as far as possible with local decisions? To the best of our knowledge no general solution other than randomly picking available adjacent node exists. Here we report some progress. Our first contribution is a new framework called tp-separate chain decomposition for studying network structures. Each tp-separate chain induces a ranking of nodes. We then prove that the ranks can be locally and distributively computed via searching some stable states of certain dynamical systems on the network and can be used to search long paths of a guaranteed length containing any given node. Numerical analyses on a number of typical real-world networks demonstrate the effectiveness of the approach.



قيم البحث

اقرأ أيضاً

What initial trajectory angle maximizes the arc length of an ideal projectile? We show the optimal angle, which depends neither on the initial speed nor on the acceleration of gravity, is the solution x to a surprising transcendental equation: csc(x) = coth(csc(x)), i.e., x = arccsc(y) where y is the unique positive fixed point of coth. Numerically, $x approx 0.9855 approx 56.47^circ$. The derivation involves a nice application of differentiation under the integral sign.
We study the lobby index (l-index for short) as a local node centrality measure for complex networks. The l-inde is compared with degree (a local measure), betweenness and Eigenvector centralities (two global measures) in the case of biological netwo rk (Yeast interaction protein-protein network) and a linguistic network (Moby Thesaurus II). In both networks, the l-index has poor correlation with betweenness but correlates with degree and Eigenvector. Being a local measure, one can take advantage by using the l-index because it carries more information about its neighbors when compared with degree centrality, indeed it requires less time to compute when compared with Eigenvector centrality. Results suggests that l-index produces better results than degree and Eigenvector measures for ranking purposes, becoming suitable as a tool to perform this task.
Governments have long standing interests in preventing market failures and enhancing innovation in strategic industries. Public policy regarding domestic technology is critical to both national security and economic prosperity. Governments often seek to enhance their global competitiveness by promoting private sector cooperative activity at the inter-organizational level. Research on network governance has illuminated the structure of boundary-spanning collaboration mainly for programs with immediate public or non-profit objectives. Far less research has examined how governments might accelerate private sector cooperation to prevent market failures or to enhance innovation. The theoretical contribution of this research is to suggest that government programs might catalyze cooperative activity by accelerating the preferential attachment mechanism inherent in social networks. We analyze the long-term effects of a government program on the strategic alliance network of 451 organizations in the high-tech semiconductor industry between 1987 and 1999, using stochastic network analysis methods for longitudinal social networks.
172 - Yukio Hayashi 2015
An interrelation between a topological design of network and efficient algorithm on it is important for its applications to communication or transportation systems. In this paper, we propose a design principle for a reliable routing in a store-carry- forward manner based on autonomously moving message-ferries on a special structure of fractal-like network, which consists of a self-similar tiling of equilateral triangles. As a collective adaptive mechanism, the routing is realized by a relay of cyclic message-ferries corresponded to a concatenation of the triangle cycles and using some good properties of the network structure. It is recoverable for local accidents in the hierarchical network structure. Moreover, the design principle is theoretically supported with a calculation method for the optimal service rates of message-ferries derived from a tandem queue model for stochastic processes on a chain of edges in the network. These results obtained from a combination of complex network science and computer science will be useful for developing a resilient network system.
This paper studies controlling segregation in social networks via exogenous incentives. We construct an edge formation game on a directed graph. A user (node) chooses the probability with which it forms an inter- or intra- community edge based on a u tility function that reflects the tradeoff between homophily (preference to connect with individuals that belong to the same group) and the preference to obtain an exogenous incentive. Decisions made by the users to connect with each other determine the evolution of the social network. We explore an algorithmic recommendation mechanism where the exogenous incentive in the utility function is based on weak ties which incentivizes users to connect across communities and mitigates the segregation. This setting leads to a submodular game with a unique Nash equilibrium. In numerical simulations, we explore how the proposed model can be useful in controlling segregation and echo chambers in social networks under various settings.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا