The population protocol model is a computational model for passive mobile agents. We address the leader election problem, which determines a unique leader on arbitrary communication graphs starting from any configuration. Unfortunately, self-stabilizing leader election is impossible to be solved without knowing the exact number of agents; thus, we consider loosely-stabilizing leader election, which converges to safe configurations in a relatively short time, and holds the specification (maintains a unique leader) for a relatively long time. When agents have unique identifiers, Sudo et al.(2019) proposed a protocol that, given an upper bound $N$ for the number of agents $n$, converges in $O(mN\log n)$ expected steps, where $m$ is the number of edges. When unique identifiers are not required, they also proposed a protocol that, using random numbers and given $N$, converges in $O(mN^2\log{N})$ expected steps. Both protocols have a holding time of $Ω(e^{2N})$ expected steps and use $O(\log{N})$ bits of memory. They also showed that the lower bound of the convergence time is $Ω(mN)$ expected steps for protocols with a holding time of $Ω(e^N)$ expected steps given $N$. In this paper, we propose protocols that do not require unique identifiers. These protocols achieve convergence times close to the lower bound with increasing memory usage. Specifically, given $N$ and an upper bound $Δ$ for the maximum degree, we propose two protocols whose convergence times are $O(mN\log n)$ and $O(mN\log N)$ both in expectation and with high probability. The former protocol uses random numbers, while the latter does not require them. Both protocols utilize $O(Δ\log N)$ bits of memory and hold the specification for $Ω(e^{2N})$ expected steps.

International audience

There is a growing need to anonymize data as new businesses are increasingly utilizing vast amount of unstructured text. Also, unstructured text have a risk of personal location estimation by considering location information. Nevertheless, existing generalizations do not take into location information and therefore cannot robustly handle this attack. In this study, we proposed anonymizing location information in unstructured text using knowledge graph newly constructed from an actual geographic information system. Our method has the advantages of anonymization, taking into account actual geographic information, handling abbreviations and spelling inconsistencies, and allowing for dynamic graph updates. The results of the evaluation experiments show that anonymization is more robust than existing methods against location estimation attacks without compromising its usefulness as a dataset. Also, we found that the names of organizations and places with a high probability of occurrence in unstructured text are more likely to lead to personal identification.

If there is a bias in the number of instances that make up the class in a dataset, the predicted results will be affected when applied to machine learning as training data. A method called resampling, which adjusts the number of majority and minority instances, is usually used to solve the imbalance in training data. Although resampling can eliminate imbalances, it may cause data complexity that deteriorates classification accuracy. Noise and overlap are well-known factors of data complexity. Noise is mixture of instances with features that can be classified into other classes at the time of training, and overlap represents the state in which classes cannot be linearly separated because they partially overlap each other. However, conventional methods could not consider these factors at a time, so that their classification accuracy would be not praiseworthy. In order to deal with both noise and overlap, we just need to integrate each of the methods that can deal with them. We know that there have already been established the methods to deal with each problem; however a simple integration of them may remove instances from the dataset that do not need to be removed, or may leave ones that should be removed. Therefore, we have to quantify these factors to take into account for data complexity, and have to consider more effective ways of their integration. In this paper, we propose a method for integrating well-known two resampling methods, which are called SMOTE-ENN and SMOTE-Tomek. In four out of ten datasets, our experimental result showed that our method is effective compared with the latest conventional methods.