Browsing by Subject "neighborhood"

Now showing 1 - 4 of 4

Access status: Open Access ,
Intrinsic dimensionality detection criterion based on Locally Linear Embedding
(Wydawnictwa AGH, 2018) Meng, Lian; Breitkopf, Piotr
In this work, we revisit the Locally Linear Embedding (LLE) algorithm that is widely employed in dimensionality reduction. With a particular interest to the correspondences of the nearest neighbors in the original and embedded spaces, we observe that, when prescribing low-dimensional embedding spaces, LLE remains merely a weight-preserving rather than a neighborhood-preserving algorithm. Thus, we propose a »neighborhood-preserving ratio« criterion to estimate the minimal intrinsic dimensionality required for neighborhood preservation. We validate its efficiency on sets of synthetic data, including S-curve, Swiss roll, and a dataset of grayscale images.
Access status: Open Access ,
On the hat problem on a graph
(2012) Krzywkowski, Marcin
The topic of this paper is the hat problem in which each of $n$ players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of winning. In this version every player can see everybody excluding himself. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom he is connected by an edge. The solution of the hat problem on a graph is known for trees and for cycles on four or at least nine vertices. In this paper first we give an upper bound on the maximum chance of success for graphs with neighborhood-dominated vertices. Next we solve the problem on unicyclic graphs containing a cycle on at least nine vertices. We prove that the maximum chance of success is one by two. Then we consider the hat problem on a graph with a universal vertex. We prove that there always exists an optimal strategy such that in every case some vertex guesses its color. Moreover, we prove that there exists a graph with a universal vertex for which there exists an optimal strategy such that in some case no vertex guesses its color. We also give some Nordhaus-Gaddum type inequalities.
Access status: Open Access ,
On the structure of compact graphs
(Wydawnictwa AGH, 2017) Nikandish, Reza; Shaveisi, Farzad
A simple graph $G$ is called a compact graph if $G$ contains no isolated vertices and for each pair $x$, $y$ of non-adjacent vertices of $G$, there is a vertex z with $N(x)\cup N(y)\subseteq N(z)$, where $N(v)$ is the neighborhood of $v$, for every vertex $v$ of $G.$ In this paper, compact graphs with sufficient number of edges are studied. Also, it is proved that every regular compact graph is strongly regular. Some results about cycles in compact graphs are proved, too. Among other results, it is proved that if the ascending chain condition holds for the set of neighbors of a compact graph $G$, then the descending chain condition holds for the set of neighbors of $G$.
Access status: Open Access ,
Role of digital tools in community management and urban participation (evidence of Belarus)
(Wydawnictwa AGH, 2022) Lebedeva, Elena
This article is devoted to an analysis of the »hybrid neighborhood« phenomenon. Traditionally, a Soviet residential yard is presented in urban studies as the sphere of a neighbor’s active participation. The post-Soviet changes have significantly weakened the activities of neighbor communities, however, the spread of digital communication tools (social networks and messengers) has led to an increase in civic engagement in cities (new forms of neighboring communities are created, traditions of spending time together with neighbors revived, and individuals are actively involving in the struggle for their »place in the city«). The empirical materials that are analyzed reveal the features of neighbors interacting demonstrate the differences between »neighbor« and »civil« communication modes, define the role of online communities in local self-government, and practically implement the »right to the city«.