eISSN:
 2577-8838

All Issues

Volume 1, 2018

Mathematical Foundations of Computing

August 2018 , Volume 1 , Issue 3

Select all articles

Export/Reference:

Influence analysis: A survey of the state-of-the-art
Meng Han and Yingshu Li
2018, 1(3): 201-253 doi: 10.3934/mfc.2018010 +[Abstract](890) +[HTML](682) +[PDF](2792.87KB)
Abstract:

Online social networks have seen an exponential growth in number of users and activities recently. The rapid proliferation of online social networks provides rich data and infinite possibilities for us to analyze and understand the complex inherent mechanism which governs the evolution of the new online world. This paper summarizes the state-of-art research results on social influence analysis in a broad sense. First, we review the development process of influence analysis in social networks based on several basic conceptions and features in a social aspect. Then the online social networks are discussed. After describing the classical models which simulate the influence spreading progress, we give a bird's eye view of the up-to-date literatures on influence diffusion models and influence maximization approaches. Third, we present the applications including web services, marketing, and advertisement services which based on the influence analysis. At last, we point out the research challenges and opportunities in this area for both industry and academia reference.

Total $\{k\}$-domination in special graphs
Haisheng Tan, Liuyan Liu and Hongyu Liang
2018, 1(3): 255-263 doi: 10.3934/mfc.2018011 +[Abstract](322) +[HTML](214) +[PDF](337.78KB)
Abstract:

For a positive integer \begin{document}$k$\end{document} and a graph \begin{document}$G = (V,E)$\end{document}, a function \begin{document}$f:V \to \{0,1,...,k\}$\end{document} is called a total \begin{document}$\{k\}$\end{document}-dominating function of \begin{document}$G$\end{document} if \begin{document}$\sum_{u∈ N_G(v)}f(u)≥ k$\end{document} for each \begin{document}$v∈ V$\end{document}, where \begin{document}$N_G(v)$\end{document} is the neighborhood of \begin{document}$v$\end{document} in \begin{document}$G$\end{document}. The total \begin{document}$\{k\}$\end{document}-domination number of \begin{document}$G$\end{document}, denoted by \begin{document}$\gamma _t^{\left\{ k \right\}}\left( G \right)$\end{document}, is the minimum weight of a total \begin{document}$\{k\}$\end{document}-dominating function \begin{document}$G$\end{document}, where the weight of \begin{document}$f$\end{document} is \begin{document}$\sum_{v∈ V}f(v)$\end{document}. In this paper, we determine the exact values of the total \begin{document}$\{k\}$\end{document}-domination number for several commonly-encountered classes of graphs including cycles, paths, wheels, and pans.

Discrete heat transfer search for solving travelling salesman problem
Poonam Savsani and Mohamed A. Tawhid
2018, 1(3): 265-280 doi: 10.3934/mfc.2018012 +[Abstract](365) +[HTML](401) +[PDF](865.09KB)
Abstract:

Within the academic circle the Traveling Salesman Problem (TSP), this is one of the most major NP-hard problems that have been a primary topic of discussion for years. Developing efficient algorithms to solve TSP have been the goal of many individuals, and so this has been addressed efficiently in this article. Here, a discrete heat transfer search (DHTS) is proposed to solve TSP. DHTS uses three distinct phases to update the city tours namely, conduction, convection, and radiation. Each phase performs a certain function as the conduction phase is a replica of the 2-Opt local search technique, the convection phase exchanges the random city with the finest city tour, and the radiation phase exchanges the random city among two separate city tours without compromising the basics of HTS algorithm. Bench test problems taken from TSPLIB successfully test the algorithm and demonstrate the fact that the proposed algorithm can attain results near the optimal values, and do so within an acceptable duration.

Improve symmetry of arbiter in APUF
Yang Xu, Huansheng Ning, Lingfeng Mao, Youzhong Li and Lijun Zhang
2018, 1(3): 281-294 doi: 10.3934/mfc.2018013 +[Abstract](337) +[HTML](229) +[PDF](1737.1KB)
Abstract:

Arbiter-based physical unclonable function (APUF) is a classical kind of physical unclonable function (PUF). In APUF-based device authentication, the fairness of traditional APUF is insufficient due to setup time of arbiter. To solve this problem, in this paper we design an arbiter and conduct Monte Carlo simulations to test the performance of the new arbiter. In addition, we present some new evaluation metrics to evaluate the new arbiter quantitatively. Finally, we certify that the new arbiter can work continuously with both one stage racing paths and eight stages racing paths. The new arbiter has good performance in correct rate, stability and fairness. Particularly, it mitigates the setup time problem by reducing the Asymmetry.

A real-time aggregate data publishing scheme with adaptive ω-event differential privacy
Chengtao Yong, Yan Huo, Chunqiang Hu, Yanfei Lu and Guanlin Jing
2018, 1(3): 295-309 doi: 10.3934/mfc.2018014 +[Abstract](301) +[HTML](295) +[PDF](1304.61KB)
Abstract:

Although massive real-time data collected from users can provide benefits to improve the quality of human daily lives, it is possible to expose users' privacy. \begin{document}$\epsilon$\end{document}-differential privacy is a notable model to provide strong privacy preserving in statistics. The existing works highlight \begin{document}$ω$\end{document}-event differential privacy with a fixed window size, which may not be suitable for many practical scenarios. In view of this issue, we explore a real-time scheme with adaptive \begin{document}$ω$\end{document}-event for differentially private time-series publishing (ADP) in this paper. In specific, we define a novel notion, Quality of Privacy (QoP) to measure both the utility of the released statistics and the performance of privacy preserving. According to this, we present an adaptive \begin{document}$ω$\end{document}-event differential privacy model that can provide privacy protection with higher accuracy and better privacy protection effect. In addition, we also design a smart grouping mechanism to improve the grouping performance, and then improve the availability of publishing statistics. Finally, comparing with the existing schemes, we exploit real-world and synthetic datasets to conduct several experiments to demonstrate the superior performance of the ADP scheme.

Editors

Referees

Librarians

Email Alert

[Back to Top]