As a combination of edge computing and artificial intelligence,edge intelligence has become a promising technique and provided its users with a series of fast,precise,and customized services.In edge intelligence,when ...As a combination of edge computing and artificial intelligence,edge intelligence has become a promising technique and provided its users with a series of fast,precise,and customized services.In edge intelligence,when learning agents are deployed on the edge side,the data aggregation from the end side to the designated edge devices is an important research topic.Considering the various importance of end devices,this paper studies the weighted data aggregation problem in a single hop end-to-edge communication network.Firstly,to make sure all the end devices with various weights are fairly treated in data aggregation,a distributed end-to-edge cooperative scheme is proposed.Then,to handle the massive contention on the wireless channel caused by end devices,a multi-armed bandit(MAB)algorithm is designed to help the end devices find their most appropriate update rates.Diffe-rent from the traditional data aggregation works,combining the MAB enables our algorithm a higher efficiency in data aggregation.With a theoretical analysis,we show that the efficiency of our algorithm is asymptotically optimal.Comparative experiments with previous works are also conducted to show the strength of our algorithm.展开更多
With the enhancement of data collection capabilities,massive streaming data have been accumulated in numerous application scenarios.Specifically,the issue of classifying data streams based on mobile sensors can be for...With the enhancement of data collection capabilities,massive streaming data have been accumulated in numerous application scenarios.Specifically,the issue of classifying data streams based on mobile sensors can be formalized as a multi-task multi-view learning problem with a specific task comprising multiple views with shared features collected from multiple sensors.Existing incremental learning methods are often single-task single-view,which cannot learn shared representations between relevant tasks and views.An adaptive multi-task multi-view incremental learning framework for data stream classification called MTMVIS is proposed to address the above challenges,utilizing the idea of multi-task multi-view learning.Specifically,the attention mechanism is first used to align different sensor data of different views.In addition,MTMVIS uses adaptive Fisher regularization from the perspective of multi-task multi-view learning to overcome catastrophic forgetting in incremental learning.Results reveal that the proposed framework outperforms state-of-the-art methods based on the experiments on two different datasets with other baselines.展开更多
Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied co...Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.展开更多
The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few inde...The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.展开更多
Most blockchain systems currently adopt resource-consuming protocols to achieve consensus between miners;for example,the Proof-of-Work(PoW)and Practical Byzantine Fault Tolerant(PBFT)schemes,which have a high consumpt...Most blockchain systems currently adopt resource-consuming protocols to achieve consensus between miners;for example,the Proof-of-Work(PoW)and Practical Byzantine Fault Tolerant(PBFT)schemes,which have a high consumption of computing/communication resources and usually require reliable communications with bounded delay.However,these protocols may be unsuitable for Internet of Things(IoT)networks because the IoT devices are usually lightweight,battery-operated,and deployed in an unreliable wireless environment.Therefore,this paper studies an efficient consensus protocol for blockchain in IoT networks via reinforcement learning.Specifically,the consensus protocol in this work is designed on the basis of the Proof-of-Communication(PoC)scheme directly in a single-hop wireless network with unreliable communications.A distributed MultiAgent Reinforcement Learning(MARL)algorithm is proposed to improve the efficiency and fairness of consensus for miners in the blockchain system.In this algorithm,each agent uses a matrix to depict the efficiency and fairness of the recent consensus and tunes its actions and rewards carefully in an actor-critic framework to seek effective performance.Empirical results from the simulation show that the fairness of consensus in the proposed algorithm is guaranteed,and the efficiency nearly reaches a centralized optimal solution.展开更多
Edge intelligence is an emerging technology that enables artificial intelligence on connected systems and devices in close proximity to the data sources.decentralized collaborative learning(DCL)is a novel edge intelli...Edge intelligence is an emerging technology that enables artificial intelligence on connected systems and devices in close proximity to the data sources.decentralized collaborative learning(DCL)is a novel edge intelligence technique that allows distributed clients to cooperatively train a global learning model without revealing their data.DCL has a wide range of applications in various domains,such as smart city and autonomous driving.However,DCL faces significant challenges in ensuring its trustworthiness,as data isolation and privacy issues make DCL systems vulnerable to adversarial attacks that aim to breach system confidentiality,undermine learning reliability or violate data privacy.Therefore,it is crucial to design DCL in a trustworthy manner,with a focus on security,robustness,and privacy.In this survey,we present a comprehensive review of existing efforts for designing trustworthy DCL systems from the three key aformentioned aspects:security,robustness,and privacy.We analyze the threats that affect the trustworthiness of DCL across different scenarios and assess specific technical solutions for achieving each aspect of trustworthy DCL(TDCL).Finally,we highlight open challenges and future directions for advancing TDCL research and practice.展开更多
Metaverse has rekindled human beings’desire to further break space-time barriers by fusing the virtual and real worlds.However,security and privacy threats hinder us from building a utopia.A metaverse em-braces vario...Metaverse has rekindled human beings’desire to further break space-time barriers by fusing the virtual and real worlds.However,security and privacy threats hinder us from building a utopia.A metaverse em-braces various techniques,while at the same time inheriting their pitfalls and thus exposing large attack surfaces.Blockchain,proposed in 2008,was regarded as a key building block of metaverses.it enables transparent and trusted computing environments using tamper-resistant decentralized ledgers.Currently,blockchain supports Decentralized Finance(DeFi)and Non-fungible Tokens(NFT)for metaverses.How-ever,the power of a blockchain has not been sufficiently exploited.In this article,we propose a novel trustless architecture of blockchain-enabled metaverse,aiming to provide efficient resource integration and allocation by consolidating hardware and software components.To realize our design objectives,we provide an On-Demand Trusted Computing Environment(OTCE)technique based on local trust evalua-tion.Specifically,the architecture adopts a hypergraph to represent a metaverse,in which each hyper-edge links a group of users with certain relationship.Then the trust level of each user group can be evaluated based on graph analytics techniques.Based on the trust value,each group can determine its security plan on demand,free from interference by irrelevant nodes.Besides,OTCEs enable large-scale and flexible application environments(sandboxes)while preserving a strong security guarantee.展开更多
In recent years,due to the wide implementation of mobile agents,the Internet-of-Things(IoT) networks have been applied in several real-life scenarios,servicing applications in the areas of public safety,proximity-base...In recent years,due to the wide implementation of mobile agents,the Internet-of-Things(IoT) networks have been applied in several real-life scenarios,servicing applications in the areas of public safety,proximity-based services,and fog computing.Meanwhile,when more complex tasks are processed in IoT networks,demands on identity authentication,certifiable traceability,and privacy protection for services in IoT networks increase.Building a blockchain system in IoT networks can greatly satisfy such demands.However,the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions,especially in terms of achieving consensus on each block in complex wireless environments,which directly motivates our work.In this study,we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks,including the negative impacts caused by contention and interference in wireless channel,and the lack of reliable transmissions and prior network organizations.By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks,we showed that it is possible to directly reach a consensus for blockchains in IoT networks,without relying on any additional network layers or protocols to provide reliable and ordered communications.In our theoretical analysis,we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving.The extensive simulation results also validate our conclusions in the theoretical analysis.展开更多
In the era of big data,sensor networks have been pervasively deployed,producing a large amount of data for various applications.However,because sensor networks are usually placed in hostile environments,managing the h...In the era of big data,sensor networks have been pervasively deployed,producing a large amount of data for various applications.However,because sensor networks are usually placed in hostile environments,managing the huge volume of data is a very challenging issue.In this study,we mainly focus on the data storage reliability problem in heterogeneous wireless sensor networks where robust storage nodes are deployed in sensor networks and data redundancy is utilized through coding techniques.To minimize data delivery and data storage costs,we design an algorithm to jointly optimize data routing and storage node deployment.The problem can be formulated as a binary nonlinear combinatorial optimization problem,and due to its NP-hardness,designing approximation algorithms is highly nontrivial.By leveraging the Markov approximation framework,we elaborately design an efficient algorithm driven by a continuous-time Markov chain to schedule the deployment of the storage node and corresponding routing strategy.We also perform extensive simulations to verify the efficacy of our algorithm.展开更多
In the past decades,with the widespread implementation of wireless networks,such as the Internet of Things,an enormous demand for designing relative algorithms for various realistic scenarios has arisen.However,with t...In the past decades,with the widespread implementation of wireless networks,such as the Internet of Things,an enormous demand for designing relative algorithms for various realistic scenarios has arisen.However,with the widening of scales and deepening of network layers,it has become increasingly challenging to design such algorithms when the issues of message dissemination at high levels and the contention management at the physical layer are considered.Accordingly,the abstract medium access control(absMAC)layer,which was proposed in2009,is designed to solve this problem.Specifically,the absMAC layer consists of two basic operations for network agents:the acknowledgement operation to broadcast messages to all neighbors and the progress operation to receive messages from neighbors.The absMAC layer divides the wireless algorithm design into two independent and manageable components,i.e.,to implement the absMAC layer over a physical network and to solve higher-level problems based on the acknowledgement and progress operations provided by the absMAC layer,which makes the algorithm design easier and simpler.In this study,we consider the implementation of the absMAC layer under jamming.An efficient algorithm is proposed to implement the absMAC layer,attached with rigorous theoretical analyses and extensive simulation results.Based on the implemented absMAC layer,many high-level algorithms in non-jamming cases can be executed in a jamming network.展开更多
Community search has been extensively studied in large networks,such as Protein-Protein Interaction(PPI)networks,citation graphs,and collaboration networks.However,in terms of widely existing multi-valued networks,whe...Community search has been extensively studied in large networks,such as Protein-Protein Interaction(PPI)networks,citation graphs,and collaboration networks.However,in terms of widely existing multi-valued networks,where each node has d(d 1)numerical attributes,almost all existing algorithms either completely ignore the attributes of node at all or only consider one attribute.To solve this problem,the concept of skyline community was presented,based on the concepts of k-core and skyline recently.The skyline community is defined as a maximal k-core that satisfies some influence constraints,which is very useful in depicting the communities that are not dominated by other communities in multi-valued networks.However,the algorithms proposed on skyline community search can only work in the special case that the nodes have different values on each attribute,and the computation complexity degrades exponentially as the number of attributes increases.In this work,we turn our attention to the general scenario where multiple nodes may have the same attribute value.Specifically,we first present an algorithm,called MICS,which can find all skyline communities in a multi-valued network.To improve computation efficiency,we then propose a dimension reduction based algorithm,called P-MICS,using the maximum entropy method.Our algorithm can significantly reduce the skyline community searching time,while is still able to find almost all cohesive skyline communities.Extensive experiments on real-world datasets demonstrate the efficiency and effectiveness of our algorithms.展开更多
A public-private-graph(pp-graph)is developed to model social networks with hidden relationships,and it consists of one public graph in which edges are visible to all users,and multiple private graphs in which edges ar...A public-private-graph(pp-graph)is developed to model social networks with hidden relationships,and it consists of one public graph in which edges are visible to all users,and multiple private graphs in which edges are only visible to its endpoint users.In contrast with conventional graphs where the edges can be visible to all users,it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph.In this paper,we first propose a novel concept,public-private-core(pp-core)number based on the k-core number,which integrally considers both the public graph and private graphs of vertices,to measure how critical a user is.We then give an efficient algorithm for the pp-core number computation,which takes only linear time and space.Considering that the graphs can be always evolving over time,we also present effective algorithms for pp-core maintenance after the graph changes,avoiding redundant re-computation of pp-core number.Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability.Compared to recalculating the pp-core numbers of all vertices,our maintenance algorithms can reduce the computation time by about 6-8 orders of magnitude.展开更多
基金supported by the National Natural Science Foundation of China(NSFC)(62102232,62122042,61971269)Natural Science Foundation of Shandong Province Under(ZR2021QF064)。
文摘As a combination of edge computing and artificial intelligence,edge intelligence has become a promising technique and provided its users with a series of fast,precise,and customized services.In edge intelligence,when learning agents are deployed on the edge side,the data aggregation from the end side to the designated edge devices is an important research topic.Considering the various importance of end devices,this paper studies the weighted data aggregation problem in a single hop end-to-edge communication network.Firstly,to make sure all the end devices with various weights are fairly treated in data aggregation,a distributed end-to-edge cooperative scheme is proposed.Then,to handle the massive contention on the wireless channel caused by end devices,a multi-armed bandit(MAB)algorithm is designed to help the end devices find their most appropriate update rates.Diffe-rent from the traditional data aggregation works,combining the MAB enables our algorithm a higher efficiency in data aggregation.With a theoretical analysis,we show that the efficiency of our algorithm is asymptotically optimal.Comparative experiments with previous works are also conducted to show the strength of our algorithm.
文摘With the enhancement of data collection capabilities,massive streaming data have been accumulated in numerous application scenarios.Specifically,the issue of classifying data streams based on mobile sensors can be formalized as a multi-task multi-view learning problem with a specific task comprising multiple views with shared features collected from multiple sensors.Existing incremental learning methods are often single-task single-view,which cannot learn shared representations between relevant tasks and views.An adaptive multi-task multi-view incremental learning framework for data stream classification called MTMVIS is proposed to address the above challenges,utilizing the idea of multi-task multi-view learning.Specifically,the attention mechanism is first used to align different sensor data of different views.In addition,MTMVIS uses adaptive Fisher regularization from the perspective of multi-task multi-view learning to overcome catastrophic forgetting in incremental learning.Results reveal that the proposed framework outperforms state-of-the-art methods based on the experiments on two different datasets with other baselines.
基金supported in part by the National Key Research and Development Program of China(No.2020YFB1005900)in part by National Natural Science Foundation of China(No.62122042)in part by Shandong University Multidisciplinary Research and Innovation Team of Young Scholars(No.2020QNQT017)。
文摘Large-scale graphs usually exhibit global sparsity with local cohesiveness,and mining the representative cohesive subgraphs is a fundamental problem in graph analysis.The k-truss is one of the most commonly studied cohesive subgraphs,in which each edge is formed in at least k 2 triangles.A critical issue in mining a k-truss lies in the computation of the trussness of each edge,which is the maximum value of k that an edge can be in a k-truss.Existing works mostly focus on truss computation in static graphs by sequential models.However,the graphs are constantly changing dynamically in the real world.We study distributed truss computation in dynamic graphs in this paper.In particular,we compute the trussness of edges based on the local nature of the k-truss in a synchronized node-centric distributed model.Iteratively decomposing the trussness of edges by relying only on local topological information is possible with the proposed distributed decomposition algorithm.Moreover,the distributed maintenance algorithm only needs to update a small amount of dynamic information to complete the computation.Extensive experiments have been conducted to show the scalability and efficiency of the proposed algorithm.
基金This work was supported by the National Key Research and Development Program of China(No.2019YFB2102600)the National Natural Science Foundation of China(Nos.62122042 and 61971269)the Blockchain Core Technology Strategic Research Program of Ministry of Education of China(No.2020KJ010301)fund。
文摘The prevalence of graph data has brought a lot of attention to cohesive and dense subgraph mining.In contrast with the large number of indexes proposed to help mine dense subgraphs in general graphs,only very few indexes are proposed for the same in bipartite graphs.In this work,we present the index called˛.ˇ/-core number on vertices,which reflects the maximal cohesive and dense subgraph a vertex can be in,to help enumerate the(α,β)-cores,a commonly used dense structure in bipartite graphs.To address the problem of extremely high time and space cost for enumerating the(α,β)-cores,we first present a linear time and space algorithm for computing the˛.ˇ/-core numbers of vertices.We further propose core maintenance algorithms,to update the core numbers of vertices when a graph changes by avoiding recalculations.Experimental results on different real-world and synthetic datasets demonstrate the effectiveness and efficiency of our algorithms.
基金This work was partially supported by the National Key Research and Development Program of China(No.2020YFB1005900)the National Natural Science Foundation of China(Nos.62102232,62122042,and 61971269)the Natural Science Foundation of Shandong Province(No.ZR2021QF064).
文摘Most blockchain systems currently adopt resource-consuming protocols to achieve consensus between miners;for example,the Proof-of-Work(PoW)and Practical Byzantine Fault Tolerant(PBFT)schemes,which have a high consumption of computing/communication resources and usually require reliable communications with bounded delay.However,these protocols may be unsuitable for Internet of Things(IoT)networks because the IoT devices are usually lightweight,battery-operated,and deployed in an unreliable wireless environment.Therefore,this paper studies an efficient consensus protocol for blockchain in IoT networks via reinforcement learning.Specifically,the consensus protocol in this work is designed on the basis of the Proof-of-Communication(PoC)scheme directly in a single-hop wireless network with unreliable communications.A distributed MultiAgent Reinforcement Learning(MARL)algorithm is proposed to improve the efficiency and fairness of consensus for miners in the blockchain system.In this algorithm,each agent uses a matrix to depict the efficiency and fairness of the recent consensus and tunes its actions and rewards carefully in an actor-critic framework to seek effective performance.Empirical results from the simulation show that the fairness of consensus in the proposed algorithm is guaranteed,and the efficiency nearly reaches a centralized optimal solution.
基金funded in part by the National Natural Science Foundation of China(62122042,62202273 and 62302247)the Fundamental Research Funds for the Central Universities(2022JC016)+1 种基金the Major Basic Research Program of Shandong Provincial Natural Science Foundation(ZR2022ZD02)Shandong Provincial Natural Science Foundation(ZR2021QF044 and ZR2022QF140).
文摘Edge intelligence is an emerging technology that enables artificial intelligence on connected systems and devices in close proximity to the data sources.decentralized collaborative learning(DCL)is a novel edge intelligence technique that allows distributed clients to cooperatively train a global learning model without revealing their data.DCL has a wide range of applications in various domains,such as smart city and autonomous driving.However,DCL faces significant challenges in ensuring its trustworthiness,as data isolation and privacy issues make DCL systems vulnerable to adversarial attacks that aim to breach system confidentiality,undermine learning reliability or violate data privacy.Therefore,it is crucial to design DCL in a trustworthy manner,with a focus on security,robustness,and privacy.In this survey,we present a comprehensive review of existing efforts for designing trustworthy DCL systems from the three key aformentioned aspects:security,robustness,and privacy.We analyze the threats that affect the trustworthiness of DCL across different scenarios and assess specific technical solutions for achieving each aspect of trustworthy DCL(TDCL).Finally,we highlight open challenges and future directions for advancing TDCL research and practice.
文摘Metaverse has rekindled human beings’desire to further break space-time barriers by fusing the virtual and real worlds.However,security and privacy threats hinder us from building a utopia.A metaverse em-braces various techniques,while at the same time inheriting their pitfalls and thus exposing large attack surfaces.Blockchain,proposed in 2008,was regarded as a key building block of metaverses.it enables transparent and trusted computing environments using tamper-resistant decentralized ledgers.Currently,blockchain supports Decentralized Finance(DeFi)and Non-fungible Tokens(NFT)for metaverses.How-ever,the power of a blockchain has not been sufficiently exploited.In this article,we propose a novel trustless architecture of blockchain-enabled metaverse,aiming to provide efficient resource integration and allocation by consolidating hardware and software components.To realize our design objectives,we provide an On-Demand Trusted Computing Environment(OTCE)technique based on local trust evalua-tion.Specifically,the architecture adopts a hypergraph to represent a metaverse,in which each hyper-edge links a group of users with certain relationship.Then the trust level of each user group can be evaluated based on graph analytics techniques.Based on the trust value,each group can determine its security plan on demand,free from interference by irrelevant nodes.Besides,OTCEs enable large-scale and flexible application environments(sandboxes)while preserving a strong security guarantee.
基金supported by the National Key Research and Development Program of China (No. 2020YFB1005900)the National Natural Science Foundation of China (NSFC) (Nos. 6212200494,61971269,and 6210070740)。
文摘In recent years,due to the wide implementation of mobile agents,the Internet-of-Things(IoT) networks have been applied in several real-life scenarios,servicing applications in the areas of public safety,proximity-based services,and fog computing.Meanwhile,when more complex tasks are processed in IoT networks,demands on identity authentication,certifiable traceability,and privacy protection for services in IoT networks increase.Building a blockchain system in IoT networks can greatly satisfy such demands.However,the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions,especially in terms of achieving consensus on each block in complex wireless environments,which directly motivates our work.In this study,we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks,including the negative impacts caused by contention and interference in wireless channel,and the lack of reliable transmissions and prior network organizations.By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks,we showed that it is possible to directly reach a consensus for blockchains in IoT networks,without relying on any additional network layers or protocols to provide reliable and ordered communications.In our theoretical analysis,we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving.The extensive simulation results also validate our conclusions in the theoretical analysis.
基金partially supported by the Shandong Provincial Natural Science Foundation(No.ZR2017QF005)the National Natural Science Foundation of China(Nos.61702304,61971269,61832012,61602195,61672321,61771289,and 61602269)the China Postdoctoral Science Foundation(No.2017M622136)。
文摘In the era of big data,sensor networks have been pervasively deployed,producing a large amount of data for various applications.However,because sensor networks are usually placed in hostile environments,managing the huge volume of data is a very challenging issue.In this study,we mainly focus on the data storage reliability problem in heterogeneous wireless sensor networks where robust storage nodes are deployed in sensor networks and data redundancy is utilized through coding techniques.To minimize data delivery and data storage costs,we design an algorithm to jointly optimize data routing and storage node deployment.The problem can be formulated as a binary nonlinear combinatorial optimization problem,and due to its NP-hardness,designing approximation algorithms is highly nontrivial.By leveraging the Markov approximation framework,we elaborately design an efficient algorithm driven by a continuous-time Markov chain to schedule the deployment of the storage node and corresponding routing strategy.We also perform extensive simulations to verify the efficacy of our algorithm.
基金partially supported by the National Key R&D Program of China(No.2019YFB2102600)the National Natural Science Foundation of China(NSFC)(No.61971269)。
文摘In the past decades,with the widespread implementation of wireless networks,such as the Internet of Things,an enormous demand for designing relative algorithms for various realistic scenarios has arisen.However,with the widening of scales and deepening of network layers,it has become increasingly challenging to design such algorithms when the issues of message dissemination at high levels and the contention management at the physical layer are considered.Accordingly,the abstract medium access control(absMAC)layer,which was proposed in2009,is designed to solve this problem.Specifically,the absMAC layer consists of two basic operations for network agents:the acknowledgement operation to broadcast messages to all neighbors and the progress operation to receive messages from neighbors.The absMAC layer divides the wireless algorithm design into two independent and manageable components,i.e.,to implement the absMAC layer over a physical network and to solve higher-level problems based on the acknowledgement and progress operations provided by the absMAC layer,which makes the algorithm design easier and simpler.In this study,we consider the implementation of the absMAC layer under jamming.An efficient algorithm is proposed to implement the absMAC layer,attached with rigorous theoretical analyses and extensive simulation results.Based on the implemented absMAC layer,many high-level algorithms in non-jamming cases can be executed in a jamming network.
基金partially supported by the National Key R&D Program of China(No.2019YFB2102600)the National Natural Science Foundation of China(Nos.61971269,61832012,616727321,and 61771289)
文摘Community search has been extensively studied in large networks,such as Protein-Protein Interaction(PPI)networks,citation graphs,and collaboration networks.However,in terms of widely existing multi-valued networks,where each node has d(d 1)numerical attributes,almost all existing algorithms either completely ignore the attributes of node at all or only consider one attribute.To solve this problem,the concept of skyline community was presented,based on the concepts of k-core and skyline recently.The skyline community is defined as a maximal k-core that satisfies some influence constraints,which is very useful in depicting the communities that are not dominated by other communities in multi-valued networks.However,the algorithms proposed on skyline community search can only work in the special case that the nodes have different values on each attribute,and the computation complexity degrades exponentially as the number of attributes increases.In this work,we turn our attention to the general scenario where multiple nodes may have the same attribute value.Specifically,we first present an algorithm,called MICS,which can find all skyline communities in a multi-valued network.To improve computation efficiency,we then propose a dimension reduction based algorithm,called P-MICS,using the maximum entropy method.Our algorithm can significantly reduce the skyline community searching time,while is still able to find almost all cohesive skyline communities.Extensive experiments on real-world datasets demonstrate the efficiency and effectiveness of our algorithms.
文摘A public-private-graph(pp-graph)is developed to model social networks with hidden relationships,and it consists of one public graph in which edges are visible to all users,and multiple private graphs in which edges are only visible to its endpoint users.In contrast with conventional graphs where the edges can be visible to all users,it lacks accurate indexes to evaluate the importance of a vertex in a pp-graph.In this paper,we first propose a novel concept,public-private-core(pp-core)number based on the k-core number,which integrally considers both the public graph and private graphs of vertices,to measure how critical a user is.We then give an efficient algorithm for the pp-core number computation,which takes only linear time and space.Considering that the graphs can be always evolving over time,we also present effective algorithms for pp-core maintenance after the graph changes,avoiding redundant re-computation of pp-core number.Extension experiments conducted on real-world social networks show that our algorithms achieve good efficiency and stability.Compared to recalculating the pp-core numbers of all vertices,our maintenance algorithms can reduce the computation time by about 6-8 orders of magnitude.