Search

Link prediction aims at predicting the missing links or new links based on known topological or attribute information of networks, which is one of the most significant and challenging tasks in complex network analysis. Recently, many local similarity-based methods have been proposed and they performed well in most cases. However, most of these methods simultaneously ignore the contributions of the local structure information between endpoints and their common neighbors, as well as transmission abilities of different 3-hop paths. To address these issues, in this paper, we propose a novel link prediction method that aims at improving the prediction accuracy of the existing local similarity-based methods by integrating with local structure information and node degree information along 3-hop paths. Extensive experiments have been performed on nine real-world networks and the results demonstrate that our proposed method is superior to the existing state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Due to its widespread application in the field of public security, anomaly detection in crowd scenes has recently become a hot topic. Some deep learning-based methods led to significant accomplishments in this field. Nevertheless, due to the scarcity of data and the misclassification of queries which most of them suffer to some extent from a sudden and infrequent overfitting. Though, we tried to solve the above problems, understand the long video streams and establish an accurate and reliable security system in order to improve its performance in detecting anomalies. We also referred to the hash technique, which has proven to be the most efficient method used when researching about large-scale image recovery. Thus, this article offers a smart video anomaly detection solution. In this paper, we combine the advantages of both deep hashing and deep auto-encoders to show that tracking changes in deep hash components across time and can be used to detect local anomalies. More precisely, we start with a new technique to minimize the mass of input data and information in order to decrease the time of calculation using a new dynamic frame skipping technique. Then, we propose to measure local anomalies by combining semantic with low-level optical flows to balance the performance and perceptibility. The experimental results illustrate that the proposed methods surpass these baselines for the detection and localization of anomalies. [ABSTRACT FROM AUTHOR]

Large heterogeneous computing systems are composed of conventional central processing units and graphics processing units (GPUs) where communication plays a crucial role for system performance. This paper presents an energy consumption analytical model in terms of communication perception for the communication–computing pipeline characterization of discrete GPUs systems. We propose a dynamically adaptive energy-efficient task assignment approach, which harnesses particle swarm optimization. Static energy optimization is addressed by optimal task partition granularity. The experimental results demonstrate that the communication-based energy optimization algorithms can be more energy-saving than those without communication consideration. For some application benchmarks, the energy consumption can be saved by up to 31%. This implies the potential that the energy-saving optimization methods can be incorporated in system engineering processes. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is |$O(n(L+l))$| steps, where |$n$| is the number of nodes and |$L$| and |$l$| are the grid dimensions. [ABSTRACT FROM AUTHOR]

The proliferation of smartphones has given exponential rise to the number of new mobile malware. These malware programs are employing stealthy obfuscations to hide their malicious activities. To perform malicious activities a program must make application programming interface (API) calls. Unlike dynamic, static analysis can find all the API call paths but have some issues: large number of features; higher false positives when features reduced; and lowering false positives increases the detection rate. Certain Android API calls, e.g. android.app.Activity:boolean requestWindowFeature(int) enable malware programs to call other APIs to hide their activities. We call them leading APIs as they can lead to malicious activities. To overcome these issues, we propose new heuristics and feature groupings for building a Leading API-call Map, named LAM. We create LAM from a dominant (leading) API call tree. Dominance is a transitive relation and hence enumerates all the call sequences that a leading API leads to. LAM substantially reduces the number and improves the quality of features for combating obfuscations and detecting suspicious call sequences with few false positives. For the dataset used in this paper, LAM reduced the number of features from 509 607 to 29 977. Using 10-fold cross-validation, LAM achieved an accuracy of 97.9% with 0.4% false positives. [ABSTRACT FROM AUTHOR]

In this paper, we introduced two novel collaborative filtering techniques for recommendation systems in cases of various cold-start situations and incomplete datasets. The first model establishes an asymmetric weight matrix between items without using item meta-data and eradicates the disadvantages of neighborhood approaches by automatic determination of threshold values. Our first model, z-scoREC, is also regarded as a pure deep-learning model because it performs like a vanilla auto-encoder in transforming column vectors with z -score normalization similar to batch normalization. With the second model, ImposeSVD, we aimed to enhance the shortcomings of the PureSVD in cases of cold-start and incomplete data by preserving its straightforward implementation and non-parametric form. The ImposeSVD model relies on the z-scoREC, produces synthetic new predictions for the users by decomposing the latent factors from the imposed matrix. We evaluated our method on the well-known datasets and found out that our method was outperforming similar approaches in the specific scenarios including recommendations for cold-start users, strength in cold-start systems, and diversification of long-tail item recommendations in lists. Our z-scoREC model also outperformed familiar neighbor-based approaches when operated as a recommender system and gave a closer appearance to the decomposition methods despite its simple and rigid cost framework. [ABSTRACT FROM AUTHOR]

In this paper, an image hashing scheme combining 3D space contour (TDSC) features with vector angle (VA) features is proposed. The proposed algorithm extracts the 3D contours of the local component variation features of the image and the expression changes of the local component of the image in the form of a 3D VA to improve the performance. First, the gray component of the color image is used to construct a 3D space and the contour change features of the local component of the gray image are extracted using multi-perspectives. Then, the opposite color component and the brightness component Y of the YCbCr color space are extracted from the input image. The angular features of several image components are, respectively, extracted in the 3D space. Finally, the TDSC features are combined with the VA features to obtain image hashing. The simulations demonstrate and validate that the proposed image hashing scheme not only has better classification performance compared with the other image hashing techniques but is also equipped with the performance of tamper localization. [ABSTRACT FROM AUTHOR]

To ensure privacy and security of healthcare wireless medical sensor networks (HWMSNs), several concrete constructions of efficient certificateless aggregate signature (CLAS) scheme without bilinear pairing were proposed in the last few years. However, many previous constructions of CLAS scheme were found to be impractical, which either fail to meet the claimed security or contain design flaws. For example, in some of the previous proposals, any adversary can forge a valid signature on any new message. In this paper, we first demonstrate some security issues and design flaws in the previous proposals of CLAS scheme. As follows, to further address the above deficiencies, a new construction of CLAS scheme with improved security is presented, and the formal security proof is given using Forking Lemma in the random oracle model, assuming that the discrete logarithm problem is hard. Compared with the previous CLAS schemes, our construction has similar computational costs, and it provides better security guarantees. Therefore, compared with the existing solutions, our proposal with strong security and high computational efficiency is more suitable for use in HWMSNs. [ABSTRACT FROM AUTHOR]

With the widespread use of Internet of things(IoT) devices, it generates an enormous volume of data, and it is a challenge to mine the IoT data value while ensuring security and privacy. Federated learning is a decentralized approach for training data located on edge devices, such as mobile phones and IoT devices, while keeping privacy, efficiency, and security. However, the Non-IID (non-independent and identically distributed) data, always greatly impacts the performance of the global model. In this paper, we propose a FedDynamic algorithm to solve the statistical challenge of federated learning caused by Non-IID. As Non-IID data can lead to significant differences in model parameters between edge devices, we set different weights for different devices during model aggregation to get a high-performance global model. We analyze and exact key indices (local model accuracy, local data quality, and model difference between local models and the global model), which can reflect the quality of the model, and calculate the aggregation weight for edge devices based on the key indices. Furthermore, we dynamically adjust aggregation weight based on accuracy's variety to solve weight staleness during the training process. Experiments on the MNIST, FMNIST, EMNIST, CINIC-10 and CIFAR-10 datasets show that the FedDynamic algorithm has better accuracy and convergence performance, compared to the FedAvg, FedProx and Scaffold algorithms. [ABSTRACT FROM AUTHOR]

Video hashing is a popular research topic in the fields of multimedia information and security because its fast matching and low-cost storage characteristics are widely used in many applications (video copy detection, video retrieval, video authentication, etc.). This paper describes a compact video hashing method with a rotation- and translation-invariant model (RTIM). The key contribution of this approach is that it innovatively reconstructs an input video into a 3D RTIM by combining ring partition and a pipeline histogram; this is a first in video hashing and helps make video hashes resistant to rotation and translation. Then, the proposed model is decomposed via Tucker decomposition, and the generated core tensor is used to produce a compact hash. As the core tensor is a compressed version of the original tensor, hash construction with the core tensor makes RTIM hashing compact and achieves desirable discrimination ability. Different from existing video hashing algorithms, RTIM hashing can not only resist many commonly used digital operations, especially video rotation and cyclic frame shifting, but also achieve good discrimination ability. Various experiments demonstrate the effectiveness of our algorithm. Receiver operating characteristic curve comparisons show that compared with the state-of-the-art video hashing algorithms, RTIM hashing is more robust and compact. [ABSTRACT FROM AUTHOR]

Each malware application belongs to a specific malware family, and each family has unique characteristics. However, existing Android malware detection schemes do not pay attention to the use of malware family information. If the family information is exploited well, it could improve the accuracy of malware detection. In this paper, we propose a general E nsemble framework combining F amily I nformation for Android M alware Detector , called EFIMDetector. First, eight categories of features are extracted from Android application packages. Then, we define the malware family with a large sample size as a prosperous family and construct a classifier for each prosperous family as a conspicuousness evaluator for the family characteristics. These conspicuousness evaluators are combined with a general classifier (which can be a base or ensemble classifier in itself), called the final classifier, to form a two-layer ensemble framework. For the samples of prosperous families with conspicuous family characteristics, the conspicuousness evaluators directly provide detection results. For other samples (including the samples of prosperous families with nonconspicuous family characteristics and the samples of nonprosperous families), the final classifier is responsible for detection. Seven common base classifiers and three common ensemble classifiers are used to detect malware in the experiment. The results show that the proposed ensemble framework can effectively improve the detection accuracy of these classifiers. [ABSTRACT FROM AUTHOR]

The sketch is one of the typical and widely used data structures for estimating the frequencies of items in data streams. However, since the counter sizes in traditional rectangular sketch (r- sketch) are the same, it is hard to achieve small space usage, high capacity (i.e. the maximum frequency can be recorded) and high estimated accuracy simultaneously. Moreover, when considering the high skewness of data streams, this problem will become even worse. Consequently, we propose the trapezoidal sketch (t- sketch) in this paper. In the t- sketch, different from the r- sketch, the counter sizes in different layers are different. Therefore, the low space usage and high capacity can be achieved simultaneously in the t- sketch. Moreover, based on the basic t- sketch, we propose the space-saving t- sketch and the capacity-improvement t- sketch and analyze the properties of these two t- sketches. Finally, for improving the estimation accuracy of the t- sketch further, we propose the probabilistic-based estimation error-reducing algorithm. Compared with the CM sketch, CU sketch, C sketch and A sketch, the simulation results show that the performances on space usage, capacity and estimation accuracy are improved successfully by the space-saving t- sketch and the capacity-improvement t- sketch. [ABSTRACT FROM AUTHOR]

The emergent technology has been increasingly incorporated with the tourism industry. In the digital world, social media plays an important role in identifying the most visited tourist places. More than 80% of people commonly used the social media platform called 'Twitter'. By using tweet reviews, tourists around the world know about the feelings, suggestions and opinions of most visited tourist places in the selected region. This paper recommends an approach for the development of trip planning in South India based on tourist's preferences. For the research, we use Twitter Application Programming Interface to collect information about the most visited tourist places in South India by using tweets reviews and store it as South India Tourism Tweet reviews database. This paper mainly focuses on analyzing Twitter reviews, which are very helpful to locate the most visited tourist place. In the tweets where reviews are mostly unstructured and heterogeneous, which are then classified into positive tweets, negative tweets and neutral tweets by using the preprocessing technique and machine learning algorithm called support vector machine. Performance measures are calculated by using the classification results. Finally, the results are plotted by using the classification results and performance measures as a wordcloud. This can be very useful for tourists to select the most visited tourist locations. The proposed system can satisfy individual tourist needs. [ABSTRACT FROM AUTHOR]

Parameter servers (PSs) placement is one of the most important factors for global model training on distributed deep learning. This paper formulates a novel problem for placement strategy of PSs in the dynamic available storage capacity, with the objective of minimizing the training time of the distributed deep learning under the constraints of storage capacity and the number of local PSs. Then, we provide the proof for the NP-hardness of the proposed problem. The whole training epochs are divided into two parts, i.e. the first epoch and the other epochs. For the first epoch, an approximation algorithm and a rounding algorithm are proposed in this paper, to solve the proposed problem. For the other epochs, an adjustment algorithm is proposed, by continuously adjusting the decisions for placement strategy of PSs to decrease the training time of the global model. Simulation results show that the proposed approximation algorithm and rounding algorithm perform better than existing works for all cases, in terms of the training time of global model. Meanwhile, the training time of global model for the proposed approximation algorithm is very close to that for optimal solution generated by the brute-force approach for all cases. Besides, the integrated algorithm outperforms the existing works when the available storage capacity varies during the training. [ABSTRACT FROM AUTHOR]

A number of text compression algorithms have been proposed in the past decades, which have been very effective and usually operate on conventional character/word-based approaches. A novel data compression perspective of data mining is explored in this research and the paper focuses on novel frequent sequence/pattern mining approach to text compression. This work attempts to make use of longer-range correlations between words in languages for achieving better text compression. We propose a novel and efficient method by making the compression of any word-level text in a universal manner for corpora across domains referred as Universal Huffman Tree-based encoding. The major contribution of this work is in terms of avoidance of code table communication to the decoder. Simulation results over benchmark datasets indicate that Universal Huffman encoding employing frequent sequence mining (achieves [20%, 89%] improvement in compression in reduced time. The paper also contributes a usable interface for Data compression that employs the proposed frequent sequent mining-based data compression algorithm. The interface supports features such as feedback, consistency, usability, navigation, visual appeal, performance and accessibility on par with existing compression softwares. The work results in an intelligent data compression software employing knowledge engineering perspective. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) jobs not only require computational resources but also are delay-sensitive and security-sensitive. Edge computing emerges as a promising paradigm to improve the quality of experience for IoT users. Edge computing faces many security threats, perhaps even more than traditional data centers. With a growing amount of data offloaded to Edge Data Centers (EDCs), the EDC performance needs to be considered and evaluated carefully for improving the vulnerable EDC resource utilization while satisfying IoT job requirements. This paper develops an analytical model, which can capture the dynamics of an EDC system with the following features: (i) The system is under heterogeneous workloads; (ii) the system is subject to attacks, which prevent equipment units in the system from providing service and (iii) the jobs in the system are delay-sensitive. Namely, the job processing fails before the processing is completed. Based on the proposed model, we develop formulas for performance and profit metrics and conduct a series of simulation experiments to verify the correctness and accuracy of our model. Finally, through our model, we evaluate the performance of the EDC, and we offer solutions for EDC administrators to maximize profit. [ABSTRACT FROM AUTHOR]

At CRYPTO'19, Gohr built a bridge between deep learning and cryptanalysis. Based on deep neural networks, he trained neural distinguishers of SPECK32/64. Besides, with the help of neural distinguishers, he attacked 11-round SPECK32/64 using Bayesian optimization. Compared with the traditional attack, its complexity was reduced. Although his work opened a new direction of machine learning aided cryptanalysis, there are still two research gaps that researchers are eager to fill in. (i) Can the attack using neural distinguishers be used to other block ciphers? (ii) Are there effective key recovery attacks on large-size block ciphers adopting neural distinguishers? In this paper, our core target is to propose an effective neural-aided key recovery policy to attack large-size block ciphers. For large-size block ciphers, it costs too much time in pre-computation, especially in wrong key response profile, which is the main reason why there are almost no neural aided attacks on large-size block ciphers. Fortunately, we find that there is a fatal flaw in the wrong key profile. In the some experiments of SIMON32/64 and SIMON48/96, there is a regular of change in response profiles, which implies that we can use partial response instead of the complete response. Based on this, we propose a generic key recovery attack scheme which can attack large-size block ciphers. As an application, we perform a key recovery attack on 13-round SIMON64/128, which is the first practical attack using neural distinguishers to large-size ciphers. In addition, we also attack 13-round SIMON32/64 and SIMON48/96, which also shows that the neural distinguishers can be used to other block ciphers. [ABSTRACT FROM AUTHOR]

The problem of finding the maximum independent sets (or maximum cliques) of a given graph is fundamental in graph theory and is also one of the most important in terms of the application of graph theory. Let |$A(n,d,w)$| be the size of the maximum independent set of |$Q_{n}^{(d-1,w)}$|⁠ , which is the induced subgraph of points of weight |$w$| of the |$d-1^{th}$| -power of |$n$| -dimensional hypercubes. In order to further understand and study the dependent set of |$Q_{n}^{(d-1,w)}$|⁠ , we explore its clique number and the structure of the maximum clique. This paper obtains the clique number and the structure of the maximum clique of |$Q_{n}^{(d-1,w)}$| for |$5\leq d\leq 6$|⁠. Moreover, the characterizations for |$A(n,d,w)=2$| and |$3$| are also given. [ABSTRACT FROM AUTHOR]

In Crypto'19, Gohr proposed the first deep learning-based key recovery attack on 11-round Speck32/64, which opens the direction of neural-aided cryptanalysis. Until now, neural-aided cryptanalysis still faces two problems: (i) the attack complexity estimations rely purely on practical experiments; (ii) it does not work when there are not enough neutral bits. To the best of our knowledge, we are the first to solve these two problems. In this paper, we propose a Neural-Aided Statistical Attack (NASA) that has the following advantages: (i) NASA supports estimating the theoretical complexity. (ii) NASA does not rely on any special properties including neutral bits. Moreover, we propose three methods for reducing the complexity of NASA. One of the methods, which is based on a newly proposed concept named Informative Bit that reveals an important phenomenon, makes NASA applicable to large-size ciphers. We have performed a series of experiments on round reduced Speck32/64, DES, and Speck96/96. These experiments do not only verify the correctness of NASA, but also further highlight the advantage and potential of NASA. Our work arguably raises a new direction for neural-aided cryptanalysis. [ABSTRACT FROM AUTHOR]

Aiming to the challenge of occlusion during tracking, this paper proposes an anti-occlusion tracking based on joint confidence. Under the framework of the kernel correlation filter (KCF) tracking, the dimension of the feature is extended to construct a robust target appearance model, and the size of the target is estimated during the tracking process. We first judge whether occlusion occurs or not by the measurement by combining the maximum of the detection response map with the average peak correlation energy, then design the corresponding anti-interference tracking strategy. If the occlusion does not occur during the tracking process, the KCF tracking is performed, otherwise, re-detection is introduced to locate the target position, and the region corresponding to the re-detection is added to the regulation term of the KCF for context learning. The fusion of the filter template before occlusion and the context model learned during occlusion is used to locate the target and to update the model. Experimental evaluations on the datasets OTB2013, OTB100 and TC128 show that compared with the state-of-the-art algorithms such as KCF, Siamese and other algorithms, our proposed algorithm has stronger robustness and higher tracking accuracy when occlusion occurs. [ABSTRACT FROM AUTHOR]

Multi-key fully homomorphic encryption (MFHE) supports arbitrary meaningful computations on encrypted data under different public keys even without access to the secret key, which is well tailored for the secure multiparty computation scenarios. Based on the Gentry–Sahai–Waters scheme (a single-key FHE in Crypto 2013) with the underlying learning with errors problem, MW16 scheme (Eurocrypt 2016) utilizes the method of 'linear combination procedure' (LCP) as a subroutine to construct the auxiliary information for the expanded ciphertexts of MFHE scheme. However, every party shares a common random string (CRS) to be distributed by a trusted setup, which is unpractical. Meanwhile, the noise in the auxiliary information is too much compared with the one in fresh ciphertexts. In this paper, we propose a modified MFHE scheme in the plain model, i.e. without CRS, to enhance the practicability of MFHE. Specifically, every involved party generates his own public key independent on a CRS. Then a potential improvement on the LCP is developed to provide auxiliary information, which largely reduces the noise and leads to a smaller modulus for our MFHE. Furthermore, the feasibility of our proposal is also proved by theoretical performance comparisons. [ABSTRACT FROM AUTHOR]

One of the most important problems in traffic safety is providing effective collision warnings in intersection areas. In this paper, we propose a Clothoid Curve-based Intersection Collision Warning scheme (CICW) in the Internet of Vehicles. In CICW, we first present a clothoid curve-based vehicle trajectory prediction model. In this model, vehicles can establish the trajectory prediction equations by themselves. Each vehicle solves the equations based on its internal state information, electronic map, GPS data and neighbour vehicles' state information derived from periodical beacons. The vehicle then predicates the crossing points of the predicted trajectory between itself and the neighbour vehicles. Based on the reference points, it further obtains the earliest possible collision location and then issues a warning. Extensive simulation results show that the performance of the proposed scheme achieves higher collision warning accuracy and a lower error warning ratio compared to existing schemes. [ABSTRACT FROM AUTHOR]

Dynamic searchable symmetric encryption (DSSE) with forward and backward privacy makes it possible to perform search on the outsourced encrypted database efficiently while still allowing updates under acceptable leakage. Current forward and backward private DSSE (FB-DSSE) scheme proposed by Zuo et al. cannot support conjunctive keyword query and the cloud server needs to be honest-but-curious. Recent FB-DSSE scheme supporting conjunctive keyword query proposed by Patranabis et al. cannot verify search results. On the other hand, searchable symmetric encryption scheme proposed by Wang et al. that supports conjunctive keyword query and the verification of search results cannot achieve forward and backward privacy. The problem of constructing a verifiable conjunctive FB-DSSE scheme is still open. In this paper, we propose a verifiable conjunctive dynamic searchable symmetric encryption scheme (VCDSSE). VCDSSE is a FB-DSSE scheme that additionally supports the verification of search results and conjunctive keyword query. We revisit homomorphic MAC to enable efficient verification of search results, adopt the technique of oblivious cross-tags to achieve conjunctive keyword query and utilize state chain to ensure forward and backward privacy. The formal security analysis and performance evaluation demonstrate that VCDSSE is secure and practical as compared with Mitra scheme in terms of search time. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new cryptographic primitive, called multiple blind signature (MBS), which is designed based on the integration of both normal blind signature scheme and dual signature. The major difference between a normal blind signature and an MBS is that using a normal blind signature, only one message, |$m$|⁠ , can be verified, but using an MBS, any subset, |${M}^{\prime }$|⁠ , of multiple messages in a set, |$M$|⁠ , where |${M}^{\prime}{\subseteq} M$|⁠ , can be verified. With this additional property, we will show that MBS is especially suitable for e-voting and e-cash applications. In other words, we classify these processes in two applications into two phases, on-line and off-line phases. One unique property of this design is that most time-consuming computation and interaction can be performed in advance in off-line phase. There is no cost of computation and interaction in the online phase. [ABSTRACT FROM AUTHOR]

Federated learning (FL) can learn a shared global model across multiple client devices without breaching privacy requirements. But an essential challenge is that devices in FL usually have limited network bandwidth, resulting in inefficient communication as an important bottleneck for FL implementation. Current studies try to overcome this shortcoming by compressing the number of model update bits uploaded by every client. But they did not explore the underlying reason why redundant parameters are generated. In this paper, we propose Corset-Based Federated Learning framework (CBFL) —a novel FL communication framework from the perspective of redundancy data. Instead of training full datasets on a regular network model, CBFL trains a much smaller evolution network model on extracted corset , which intrinsically reduces the overall transmission bits and obtains efficient computation while maintaining a desirable model accuracy. In CBFL, a novel Fedcorset construction algorithm at selected clients and a further distributed model evolution scheme to fit the constructed corset are included. The training model size is dynamically adapted to the corset, either removing a fraction of unimportant or adding important connections at each communication iteration. Experimental results show that CBFL transfers about 13% of communication bits and saves around 56% computing time while having only 2% destination in model accuracy. [ABSTRACT FROM AUTHOR]

As a prominent cryptographic tool, geometric searchable encryption (GSE) can be applied in many scenarios, such as location-based services (LBS), social networks and vehicle networks. Unfortunately, most of existing searchable encryption schemes supporting the functionality of geometric range searches suffer from false positives, which will lead people to make a wrong decision and further raise some serious consequences such as financial loss. In addition, some of them are designed under a symmetric system, which is not enough flexible deployed in LBS since in a symmetric system only a private key holder creates ciphertext, whereas in a public-key system anyone who holds a public key can produce ciphertext. In this paper, we intend to design a novel GSE scheme without any false positive under a public-key system supporting arbitrary geometric area searches, which is able to guarantee an accurate query result. Toward this goal, we develop a novel technique in handling the relation between a point and any convex polygon in combination with an inner product encryption, which is able to support arbitrary convex polygon range searches without any false positive. A comprehensive experiment demonstrates that, compared with the known schemes, our scheme possesses a 100% accuracy as well as an acceptable efficiency in the sense that it can guarantee that all files retrieved by users are exactly matched ones. Finally, we provide two practical examples of our GSE scheme: privacy-preserving friend-nearby notification with a common point of interest and privacy-preserving parking monitor and guiding system. [ABSTRACT FROM AUTHOR]

Query reformulation is a well-known technique intended to improve the performance of Information Retrieval Systems. Among the several available techniques, Query Expansion (QE) reformulates the initial query by adding similar terms, drawn from several sources (corpus, knowledge resources), to the query terms in order to retrieve more relevant documents. Most QE methods are based on the relationships between the original query term and candidate terms (new terms) in order to select the most similar expansion terms. In this paper, we suggested a new hybrid query reformulation through QE and term re-weighting techniques. The suggested approach aimed to demonstrate the effectiveness of QE with a semantic selection of candidate terms according to the specificity of original query terms in the improvement of retrieval performance. To this end, we exploited both relationships defined by knowledge resources and the distributed semantics, recently revealed by neural network analysis. For term re-weighting, we proposed a new semantic method based on semantic similarity measure that assigns a weight to each term of the expanded query. The conducted experiments on OHSUMED and TREC 2014 CDS test collections, including long and short queries, yielded significant results that outperformed the baseline and state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

The device equipped with a multi-homing feature optimally exploits multiple network interfaces in modern communications networks such as the Internet of Things (IoT) and machine-to-machine communication using the concurrent multipath transfer (CMT). This enhances system performance by concurrently scheduling data chunks on multiple network paths. For a while, several scheduling criteria have been developed to optimize performance. However, it has been identified that CMT still suffers from many serious problems, such as spurious retransmission, receiver buffer blocking, improper congestion window (CWND) growth, re-ordering and long round trip time, resulting in poor performance. These problems occur due to the asymmetric nature of path characteristics. Thus, this paper introduces a path rank-based CMT (R-CMT) that schedules data chunks according to the rank of the path. The proposed scheduling method calculates the rank of each network path based on the ratio of successfully received and transmitted chunks. The simulation results indicate that the proposed R-CMT scheduling achieves higher performance in terms of network latency, throughput and CWND growth. [ABSTRACT FROM AUTHOR]

Differential-linear cryptanalysis, as the combination of differential and linear cryptanalysis, is an efficient way to attack many kinds of ciphers. Recently, various refinements to this cryptanalytic technique have been proposed, especially with good effects on ARX ciphers. In the current framework of a differential-linear attack, a cipher |$E$| is often divided into three parts: a differential part |$E_1$|⁠ , a linear part |$E_2$| and a connective part |$E_m$|⁠. It is a challenging problem to deal with the connective part when building a differential-linear distinguisher, and for ARX ciphers, estimating the correlation of |$ E_m $| experimentally under given input difference |$\Delta _m$| and output linear mask |$\Gamma _m$| is the main approach so far. In this paper, we discuss the effects of |$ \Delta _{m} $| and |$ \Gamma _{m} $| on the correlation of |$ E_m $| for the first time. As a result, we propose a new strategy to find |$\Delta _m$| and |$\Gamma _m$| to build differential-linear distinguishers with high correlations for ARX ciphers based on algebraic equations derived from their round functions. For the key recovery parts of differential-linear attacks, we also find a new partitioning technique which will reduce the time complexity. Based on our new methods, we improve the differential-linear attack on 7-round Chaskey. [ABSTRACT FROM AUTHOR]

Public key encryption with keyword search is a promising primitive which enables search over encrypted data in secure data outsourcing services. In traditional construction, the associated keywords may be recovered from a given trapdoor by a malicious server through keyword guessing attacks. Therefore, the notion of public-key authenticated encryption with keyword search (PAEKS) was introduced, where a sender encrypts (and authenticates) the keywords using a receiver's public key and its secret key. In this paper, we consider the forward security for PAEKS and introduce a new primitive: forward secure public-key authenticated encryption with keyword search (FS-PAEKS), which captures the information leakage risk from previously issued queries due to the updates on the outsourced data. Technically, we embed a non-interactively agreed key into the cipher-keyword generation algorithm, and bind the cipher-keyword and the trapdoor with a set converted from algorithm-generation time. Finally, we present an efficient FS-PAEKS scheme supporting conjunctive query, and prove its forward security against chosen keyword attacks and keyword guessing attacks. To illustrate practical performance, we implement our FS-PAEKS and related PAEKS schemes based on Enron dataset in real cloud environment. [ABSTRACT FROM AUTHOR]

The conditional edge-connectivity is an important parameter to evaluate the reliability and fault tolerance of multi-processor systems. The |$n$| -dimensional bijective connection networks |$B_{n}$| contain hypercubes, crossed cubes, Möbius cubes and twisted cubes, etc. The conditional edge-connectivity of a connected graph |$G$| is the minimum cardinality of edge sets, whose deletion disconnects |$G$| and results in each remaining component satisfying property |$\mathscr{P}$|⁠. And let |$F$| be the edge set as desired. For a positive integer |$a$|⁠ , if |$\mathscr{P}$| denotes the property that the average degree of each component of |$G-F$| is no less than |$a$|⁠ , then the conditional edge-connectivity can be called the |$a$| -average degree edge-connectivity |$\overline{\lambda }_{a}(G)$|⁠. In this paper, we determine that the exact value of the |$a$| -average degree edge-connectivity of an |$n$| -dimensional bijective connection network |$\overline{\lambda }_{a}(B_{n})$| is |$(n-a)2^a$| for each |$0\leq a \leq n-1 $| and |$n\geq 1$|⁠. 1 [ABSTRACT FROM AUTHOR]

Software size estimation is a vital activity of software project planning and management. Early software size estimation is a challenging task due to the limited information available during the early phases of software development. The goal of this paper is to construct and validate early software size estimation models based on four analysis-to-design adjustment factor (ADAF)-adjusted analysis class diagram metrics (i.e. ADAF-adjusted number of classes, ADAF-adjusted number of attributes, ADAF-adjusted number of methods and ADAF-adjusted number of relationships) using stepwise multiple linear regression and leave-one-out cross-validation. Furthermore, the prediction accuracy of the best-performing proposed model is also compared with the model based on objective class points. The results of this comparison reveal that our proposed method reduces errors significantly (i.e. on average, 16% reduction in mean absolute residual and 24% reduction in mean squared error). [ABSTRACT FROM AUTHOR]

As a kind of conditional connectivity, component connectivity is an improvement of traditional connectivity, which is conducive to enhance the reliability of the network. To be specific, the |$r$| -component connectivity of a network |$G$|⁠ , written as |$c\kappa _{r}(G)$|⁠ , is defined as the minimum number of all node cuts whose removal causes the remaining network to have at least |$r$| components. Component diagnosability, as another measure of network reliability, is usually related to the number of components in the remaining network. The |$r$| -component diagnosability, written as |$ct_{r}(G)$|⁠ , is defined as the maximum number of faulty sets such that at least |$r$| components in the surviving network and all faulty nodes can be diagnosed. This paper mainly explores the relationship between component connectivity and component diagnosability of some regular networks. Once knowing the component connectivity of such a network, with the help of this relationship, we can easily obtain the component diagnosability of the network. Furthermore, we apply this relationship to some famous regular networks to obtain their component diagnosabilities under the PMC model. [ABSTRACT FROM AUTHOR]

This paper intends to propose an automated deep learning-based land cover classification model of remote sensing images. The model includes (i) pre-processing, (ii) feature extraction and (iii) classification. The captured synthetic-aperture radar (SAR) and Landsat-8 images are initially pre-processed using the Gabor filtering model. Subsequently, from SAR images the gray-level-co-occurrence matrix-based texture characteristics are extracted, and temperature vegetation index-based characteristics, normalized vegetation index-based features, normalized difference index-based features and coloration index features are extracted from Landsat-8 images. Finally, the extracted features are subjected to an optimized deep belief network (DBN), where the weight is fine-tuned by the optimization logic. For this, a new Sunflower adopted Red Deer (SARD) algorithm is introduced in this work that hybrids the concept of Red Deer algorithm and Sunflower optimization. The performance of the proposed classification model is compared over other conventional models concerning different measures. Especially, the accuracy of the presented work (SARD+DBN) for Testcase3 is 5, 7, 6 and 30% better than existing DA + DBN, JA + DBN, SLnO+DBN and LA + DBN methods, respectively. [ABSTRACT FROM AUTHOR]

Diagnosability is often considered as an important factor for measuring the self-diagnostic ability of network systems. However, classic system-level diagnosis focuses only on processor faults and ignores the objective reality of communication faults. Under real circumstances, missing edges and node failures usually occur simultaneously in multiprocessor systems (called hybrid fault circumstances). Therefore, it is important to study the diagnosability of multiprocessor systems under hybrid fault circumstances. In this paper, we propose several diagnosabilities of interconnection networks with missing edges and faulty nodes. By exploring some important relationships between diagnosability and the minimum degree of a network under hybrid fault circumstances, we present and prove the diagnosability of several classic interconnection networks, including BC (bijective connection) networks, star graphs, folded hypercubes, exchanged hypercubes, exchanged crossed cubes, k-ary n-cubes, bubble-sort star graphs and balanced hypercubes, with missing edges and broken-down nodes under the PMC (Preparata, Metze and Chien) and MM* (Maeng and Malek) models. [ABSTRACT FROM AUTHOR]

The global seasonal change and continued rapid growth have maximized the need to assess the urban dwellers' depend on vegetation for their lives, and also in the urban ecosystem resources. The conventional outcomes devoted to cropland mapping, with the help of high-quality remote sensing data's. This paper is to investigate and develop a new methodology that pertains to time series analysis for classifying the type of vegetation in a farm area of Ujani Dam located in Solapur District, Maharastra. The proposed model develops a novel adaptive time-weighted dynamic time warping (ATWDTW) for the time series analysis using the satellite images. The gathered satellite images from the farm are processed initially and subjected to analysis by ATWDTW. The TWDTW concept is optimally tuned by the new hybrid meta-heuristic algorithm termed moth flame-based bird swarm optimization (MF-BSA) for enhancing the classification performance. Regarding the false omission rate of the proposed MF-BSA-ATWDTW model attains 5.56% and 29.9% lower than SVM and K-means respectively. From the analysis, it is possible to get a deep insight into the vegetation to be done in each year, and the comparative analysis proves that the proposed model is further adaptable for experimental use in relating and explaining environmental and ecological time-series information. [ABSTRACT FROM AUTHOR]

Recent emergence in deep learning resulted in significant improvement in the segmentation accuracy of sub cortical brain structures like hippocampus and amygdala. The traditional methods of segmentation cannot produce an ideal segmentation result that exhibits issues like redundant computations, inconsistencies, coefficient variations and motion artifacts. Therefore, in this paper, an improved 3D Flatteringly Amplified Neural Network model for biomedical imaging is efficiently proposed, which can make full use of the 3D spatial information of MRI image itself to overcome the inconsistency of segmented images along with equalizing the coefficient variation of tiny region of brain image segmentation. Also while equalizing the coefficient, certain significant minute details are lost due to motion artifacts hence, the robust Amyg-Hippo Seg algorithm has been introducing that extracts the features through deep learning, and achieve high-precision segmentation, it reduced the computational complexity without neglecting minute features. In addition, the Daytona dropout function provides uncertainty information and reduces over-fitting problems. The outcome of the proposed work efficiently segments the most significant regions of hippocampus and amygdala with 97.4% accuracy. [ABSTRACT FROM AUTHOR]

The data center network HSDC is a superior candidate for building large-scale data centers, and strikes a good balance among diameter, bisection width, incremental scalability and other important characteristics in contrast to the state-of-the-art data center network architectures. The Hamiltonian property is an important indicator to measure the reliability of a network. In this paper, we study the Hamiltonian properties of HSDC's logic graph |$H_n$|⁠. Firstly, we prove that |$H_n$| is Hamiltonian-connected for |$n\geq 3$|⁠. Secondly, we propose an |$O(NlogN)$| algorithm for finding a Hamiltonian path between any two distinct nodes in |$H_n$|⁠ , where |$N$| is the number of nodes in |$H_n$|⁠. Furthermore, we consider the Hamiltonian properties of |$H_n$| with faulty elements, and prove that |$H_n$| is |$(n-3)$| -fault-tolerant Hamiltonian-connected and |$(n-2)$| -fault-tolerant Hamiltonian for |$n\geq 3$|⁠. [ABSTRACT FROM AUTHOR]

One of the biggest social problems currently facing major cities around the globe is the high rate of crime. The largest part of the social-economic loss globally is ascribed to criminal activities. Crime also has direct impacts on the nation's economy, social constructs and country's global repute. Inadequate policing capital is one of the biggest challenges facing many global economies. As a result, these resources have to be rationed. This implies that some areas will not be covered extensively thus providing favorable environs for perpetrators. To combat crime, more innovative security measures are needed. In this sense, traditional methods are being replaced with modern approaches of machine learning systems that can predict the occurrence of crime. These crime forecasts can be used by legislatures and law enforcers to make effective and informed approaches that can efficiently eradicate criminals and facilitate nation building. This paper seeks to review the literature on the application of machine learning models in crime prediction and to find the influences that have an impact on crimes in Saudi Arabia. The results show that after the four models were trained and tested, the random forest classifier had the highest accuracy of 97.84%. [ABSTRACT FROM AUTHOR]

It is well known that in many real networks, such as brain networks and scientific collaboration networks, there exist higher order nonpairwise relations among nodes, i.e. interactions between more than two nodes at a time. This simplicial structure can be described by simplicial complexes and has an important effect on topological and dynamical properties of networks involving such group interactions. In this paper, we study analytically resistance distances in iteratively growing networks with higher order interactions characterized by the simplicial structure that is controlled by a parameter |$q$|⁠. We derive exact formulas for interesting quantities about resistance distances, including Kirchhoff index, additive degree-Kirchhoff index, multiplicative degree-Kirchhoff index, as well as average resistance distance, which have found applications in various areas elsewhere. We show that the average resistance distance tends to a |$q$| -dependent constant, indicating the impact of simplicial organization on the structural robustness measured by average resistance distance. [ABSTRACT FROM AUTHOR]

The diagnosability of a multiprocessor system is of great significance in measuring the reliability and faulty tolerance of interconnection networks. In this paper, we firstly study the diagnosability of a class of Cayley graphs |$Cay(H_n,S_n)$| under the PMC model. We prove that |$Cay(H_n,S_n)-F$| keeps the strong local diagnosability property even if it has the set |$F$| of |$(m-2)$| faulty edges and |$m-2$| is maximum number of faulty edges, where |$m$| is the regular degree of |$Cay(H_n,S_n)$|⁠. Secondly, we study the diagnosability of |$Cay(H_n,S_n)$| with conditional faulty edges under the PMC model. We prove that |$Cay(H_n,S_n)-F$| keeps strong local diagnosability property even if it has the set |$F$| of |$(3m-10)$| faulty edges, provided that each vertex of |$Cay(H_n,S_n)-F$| is incident with at least two fault-free edges, where |$3m-10$| is maximum number of faulty edges. Finally, we prove that |$Cay(H_n,S_n)-F$| keeps strong local diagnosability property no matter how many edges are faulty, provided that each vertex of |$Cay(H_n,S_n)-F$| is incident with at least four fault-free edges. [ABSTRACT FROM AUTHOR]

Completing the classification of tactics and techniques in cyber threat intelligence (CTI) is an important way to obtain tactics, techniques and procedures (TTPs) and portray the behavior of cyber attacks. However, the high level of abstraction of tactics and techniques information and their presence in CTI, usually in the form of natural language text, make it difficult for traditional manual analysis methods and feature engineering-based machine learning methods to complete the classification of tactics and techniques effectively. Meanwhile, flat deep learning methods do not perform well in classifying more fine-grained techniques due to their inability to exploit the hierarchical relationship between tactics and techniques. Therefore, this paper regards the tactics and techniques of TTPs defined in Adversarial Tactics, Techniques and Common Knowledge knowledge base as labels and proposes a Convolutional Neural Network (CNN) model based on hierarchical knowledge migration and attention mechanism for classifying tactics and techniques in CTI, named HM-ACNN (CNN based on hierarchical knowledge migration and attention mechanism). HM-ACNN classifies tactics and techniques into two phases, and the underlying network model for both phases is the Attention-based CNN network. The first step in HM-ACNN is converting the CTI text into a two-dimensional image based on the word embedding model, and then start training the classification of tactics through the CNN structure based on the attention mechanism before the classification of techniques. Secondly, after the tactics classification training is completed, the tactic-to-technique knowledge migration is then completed by transforming the parameters of the CNN layer and the attention layer in the tactics classification process based on the special hierarchical relationship between tactics and techniques. Then, the classification of techniques is finished by fine-tuning. The experimental results show that HM-ACNN performs well in the tactics and techniques classification tasks, and the metric F1 values reach 93.66% and 86.29%, which are better than other models such as CNN, Recurrent Neural Network and CRNN (Recurrent Convolutional Neural Networks). [ABSTRACT FROM AUTHOR]

On-line gambling is the key illegal behaviour of public security department in most countries due to the potential threat to cyberspace security and social stability. Hence, the research on gambling domain names (GDN) classification is quite important and in great demand for academia and industry. Till now, there is very little research work on this topic. Most of the GDN training datasets in previous work were chosen from GDN blacklists provided by publicly available data sources, and the authors did not verify the authenticity and accuracy of these datasets, and the classification results are not particularly satisfactory. In this paper, certificated and textual analysis-based classification method CT-GDNC is proposed to get GDN training data set with an accuracy of 0.9776 and significantly improve the classification results of GDN. The exhaustive comparative experiments on 10K GDN obtained via Bert fine-tuning model and 10K benign data collected from Alex Top 1 million list show that the proposed method achieves new baseline result for GDN classification with classification accuracy 0.9936, precision 0.9936, F1 0.9936 and recall 0.9939. [ABSTRACT FROM AUTHOR]

Researchers have proved that emotions play vital role in a human's life. They affect our way of living, making decisions and also our way of learning. There are many methods for emotion detection in e-learning. However, each of them comes with its own set of disadvantages discussed in the literature review. In this paper, the attributes that have been identified are purely unobtrusive in nature; attributes that do not interfere with the learner's activity and less is known to them that their emotions are being monitored. A methodology is presented to detect the emotions of the learner using keystrokes, mouse clicks, forum discussions and the results of assessments. Machine learning models have been trained and tested to predict the learner's emotions. The logistic regression performed fairly well in comparison to the other algorithms with an accuracy of about 85% and cross-validation score of 86%. During this study, interesting patterns are observed in learner's emotions that are discussed. Future directions include collecting diverse data to understand emotions of learners from various age groups and observing patterns in their emotional changes. [ABSTRACT FROM AUTHOR]

Flush+Reload is a powerful access-driven cache attack in which the attacker leverages a security weakness in the X86 processor architecture to extract the private data of the victim. This attack can be mounted in a cross-core setting, where the memory deduplication is enabled and several users are sharing the same physical machine. In this paper, for the first time, we demonstrate that SEED implementation of OpenSSL 1.1.0 running inside the victim VM is vulnerable against the Flush+Reload attacks and the attacker can recover the keys of this encryption. SEED is a standard encryption algorithm that was developed by the Korea Information Security Agency (KISA) and has been used for confidential services in the Republic of Korea. Our work demonstrates that the attacker can retrieve the secret keys of SEED in 3 min in the native setup and 4 min in the cross-VM setup by performing the Flush+Reload technique. Our experimental results show that common implementation of this standard cipher is vulnerable to Flush+Reload attack in both native and cross-VM settings. To the best of our knowledge, this paper presents the first cache-based attack on a SEED block cipher. [ABSTRACT FROM AUTHOR]

Autism is difficult to recognize in young ones before twenty-four months of age. The symptoms of autism usually occur between twelve to eighteen months. If autism is detected before eighteen months, suitable treatment could be offered to the children, by which normal functioning of the brain could be attained. However, till now, there were no advanced facilities for detecting autism in children on time. That leads to many complex situations while diagnosing the disease. Hence, this paper intends to present an automatic autism detection system, in which the datasets are gathered from the UCI repository. Initially, the weighted transformation of input data is taken, which is carried out to correctly distinguish the interclass labels and reduce the dimension of data. Further, Principal Component Analysis (PCA) helps to perform the role of the dimension reduction process, from which the resultant data is considered as features. Moreover, the dimensionally reduced data as features are classified using the Deep Belief Network (DBN) that recognizes the absence or presence of autism in children. As the main contribution, this paper plans to optimize or tune the decision on the number of hidden neurons in the hidden layer, training algorithm, and activation function of DBN. This optimization process is done in such a way that the error between the predicted and actual output of DBN should be minimum. Accordingly, the optimized DBN is accomplished with the aid of a hybrid algorithm that links both the Crow Search Algorithm (CSA) and the Whale Optimization Algorithm (WOA). The adopted algorithm is known as the Whale Assisted Crow Search Algorithm (W-CSA), because the CSA principle is based on WOA. To the next of implementation, the proposed autism detection model is compared with the conventional approaches, and the results are analysed in an effective manner. Accordingly, from the analysis, it is evident that the accuracy of the proposed algorithm was 4.35%, 2.86%, 1.41%, 1.41%, and 71.43% better than Particle Swarm Optimization (PSO), FireFly (FF), Grey Wolf Optimizer (GWO), WOA, and CS (Crow Search) algorithms, respectively. [ABSTRACT FROM AUTHOR]

Parameterized complexity is an exemplary approach that extracts and exploits the power of the hidden structures of input instances to solve hard problems. The tree-width (⁠|$tw$|⁠), path-width (⁠|$pathw$|⁠), branch-width (⁠|$bw$|⁠), clique-width (⁠|$cw$|⁠), rank-width (⁠|$rw$|⁠) and boolean-width (⁠|$boolw$|⁠) are some width measures of graphs that are used as parameters. Applications of these width parameters show that dynamic programming algorithms based on a path, tree or branch decomposition can be an alternative to other existing techniques for solving hard combinatorial problems on graphs. A large number of the linear- or polynomial-time fixed parameter tractability algorithms for problems on graphs start by computing a decomposition tree of the graph with a small width. The focus of this paper is to study the exact and random boolean-widths for special graphs, real-world graphs and random graphs, as well as to check their competency compared with several other existing width parameters. In our experiments, we use graphs from TreewidthLIB, which is a set of named graphs and random graphs generated by the Erdös–Rényi model. Until now, only very limited experimental work has been carried out to determine the exact and random boolean-widths of graphs. Moreover, there are no approximation algorithms for computing the near-optimal boolean-width of a given graph. The results of this paper demonstrate that the boolean-width can be used not only in theory but also in practice and is competitive with other width parameters for real graphs. [ABSTRACT FROM AUTHOR]

Blockchain has attracted tremendous attention from both the academia and the capital market. The insertion of data in a blockchain known as anchoring makes data verifiable and independently auditable and has many potential applications. The objective of this paper is to introduce a dynamic cross-chain anchoring framework for snapshotting users' data into multiple public blockchains with the help of smart contracts. This paper starts by proposing the framework and depicting the components and workflow. Second, we design a target chain selection algorithm that combines the states of different blockchains. Using the algorithm, users can dynamically select a suitable public blockchain for anchoring tasks. Third, the virtual chain protocol is presented and achieves data anchoring orderly and integrally. Analyzation and evaluation show that the framework can enhance user experience, robustness and performance. [ABSTRACT FROM AUTHOR]

This paper intends to introduce a novel groundwater prediction model by inducing the novel hydro indices that are not yet popular in earlier techniques. As per the proposed work, statistical features like mean, median, skewness and kurtosis are estimated. Moreover, the vegetation index includes simple ratio, normalized difference vegetation index, Kauth–Thomas Tasseled cap transformation and infrared index transformation. Furthermore, a novel hydro index is formulated by combining the statistical model function with the vegetation index. Subsequently, the detection process is carried out by ensemble technique, which includes the classifiers like random forest (RF), neural network (NN), support vector machine (SVM) and deep belief network (DBN). The final predicted result is attained from DBN. The performance of the adopted model is computed to the existing models with respect to certain measures. At learning rate 50, the maximum accuracy of the proposed model is 45.65, 34.78, 58.70, 72.83, 18.48 and 23.91% better than the existing models like SVM, RF, convolutional neural network, K-nearest neighbors, NN and artificial neural network, respectively. [ABSTRACT FROM AUTHOR]

Graph partitioning is an NP-hard combinatorial optimization problem, and is a fundamental step in distributing workloads on parallel compute systems, circuit placement, and sparse matrix reordering. The proposed heuristic algorithms such as streaming graph partitioning provide solutions to large-scale graph in a reasonable amount of time. However, the ability of breaking out of local minima in existing these methods is very limited as they are simple in reflecting the connectivity between vertices in real graphs with power-law distribution characteristic. As hill climbing algorithm is a local search method, it can be adopted to improve the result of graph partitioning. However, directly adopting the existing hill climbing algorithm to graph partitioning will result in local minima and poor convergence speed during the iterative process. In this paper, we propose an improved hill climbing graph partitioning algorithm based on clustering. Instead of taking a single vertex as a basic unit, the proposed method considers a cluster consisting of a series of vertices as a hill to move during each iteration. The method uses a new metric that considers both balance and edgecuts to look for the most beneficial cluster as the hill. With these improvements, the method provides a strong power to break out of local minima and achieve an adaptive tradeoff between balance and edgecuts. Experimental results on real-world graphs show that the proposed algorithm substantially reduces edgecuts within a controlled imbalance range. [ABSTRACT FROM AUTHOR]