CN114444699B - Method for predicting the network size and reliability of hypergraph networks after deliberate attacks - Google Patents
Method for predicting the network size and reliability of hypergraph networks after deliberate attacksInfo
- Publication number
- CN114444699B CN114444699B CN202210087042.8A CN202210087042A CN114444699B CN 114444699 B CN114444699 B CN 114444699B CN 202210087042 A CN202210087042 A CN 202210087042A CN 114444699 B CN114444699 B CN 114444699B
- Authority
- CN
- China
- Prior art keywords
- network
- node
- hypergraph
- attack
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N7/00—Computing arrangements based on specific mathematical models
- G06N7/01—Probabilistic graphical models, e.g. probabilistic networks
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/15—Correlation function computation including computation of convolution operations
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Algebra (AREA)
- Computing Systems (AREA)
- Databases & Information Systems (AREA)
- Artificial Intelligence (AREA)
- Evolutionary Computation (AREA)
- Probability & Statistics with Applications (AREA)
- Operations Research (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a method for predicting the network scale and reliability of an overscan network after deliberate attack, which belongs to the technical field of overscan network attack evaluation and comprises an overscan network construction step, an overscan conversion step, a node overscan calculation assignment step, a self-consistent equation introduction step and a simulation verification step, wherein the overscan network is converted into a factor graph, the probability of the removed nodes is regulated according to the size of the node overscan by adopting the deliberate attack mode to judge and calculate the scale of the network, a self-consistent equation is introduced in the calculation, and finally the number of the nodes in the factor graph is the final scale of the network.
Description
Technical Field
The invention relates to the technical field of hypergraph network attack evaluation, in particular to a method for predicting the network scale and reliability of a hypergraph network after deliberate attack.
Background
Network security, generally refers to the security of a computer network, and in fact may also refer to the security of a computer communication network.
The computer communication network is a system for interconnecting a plurality of computers with independent functions through communication equipment and transmission media and realizing information transmission and exchange among the computers under the support of communication software, and the computer network is a system for connecting a plurality of independent computer systems, terminal equipment and data equipment which are relatively dispersed in regions by using communication means and carrying out data exchange under the control of protocols aiming at sharing resources. The fundamental purpose of computer networks is resource sharing, and communication networks are ways to realize network resource sharing, so that computer networks are secure, and corresponding computer communication networks must be secure, so that information exchange and resource sharing should be realized for network users.
Network space security has become particularly important in new times, becoming a new battlefield for gaming from country to country. The network attack method is developed from the initial random selection of a host or a server to attack, to the targeted selection of a host or a server with certain attributes (usually with high centrality) to attack, and the deliberate attack method is obviously more destructive and more harmful to the network. However, the aforementioned network is a simple network of one-to-one connection between nodes, also called a pairwise interaction network, however, as research goes deep, researchers have found that such a pairwise interaction network is insufficient to describe higher-order interactions in recent years, for example, in a scientist collaboration network, researchers abstract the partner of the same article as a plurality of connected nodes one-to-one representing their collaboration, and then after the entire scientist collaboration network is composed, we want to know which authors have composed an article together, which is impossible in a simple network, in other words, the simple network cannot express higher-order interactions between nodes, so that the concept of a supergraph network, which is one of the higher-order interactions representatives, is proposed, and can be simply understood to successfully solve the above-mentioned trouble by including a plurality of nodes in one superside by the topology of a plurality of authors in the article.
The prior attack method based on the hypergraph network only stays on random attack, namely, a certain proportion of nodes are randomly removed on the hypergraph network to study the reliability of the network (generally expressed by the proportion of the node scale in the maximum connected subgraph to the node scale in the initial network), and a great deal of experiments in the simple network all draw a conclusion that the deliberate attack has larger damage to the network compared with the random attack, so that how to realize the deliberate attack on the hypergraph network and analyze the reliability of the system after the attack and the network scale consisting of the rest functional nodes is the problem to be solved currently.
This problem is currently facing the following challenges:
(1) The network equipment rapidly grows in the Internet age, and the complexity of counting the number of the equipment increases the difficulty of building the hypergraph network in the real environment;
(2) When a network attack is performed, a node with which attribute is selected to be destroyed is still to be solved.
Disclosure of Invention
The invention aims to provide an effective evaluation method for analyzing the network scale and reliability after deliberate attack on hypergraph in a real hypergraph network environment after deliberate attack aiming at the problems.
The method for predicting the network scale and reliability of the hypergraph network after intentional attack provided by the invention comprises the following steps:
step 1, hypergraph network construction;
Collecting data from the known face-to-face contact data sets by using sliding time windows with the time interval delta t, abstracting and constructing a hypergraph network by using nodes among the data, finding out the maximum connected subgraphs in the hypergraph network formed by the data collected by each sliding time window, and constructing a hypergraph network model by aggregating all the maximum connected subgraphs after de-duplication, wherein the aggregation of different connected subgraphs into the hypergraph model is equivalent to the slow formation of a large network, namely the hypergraph, because the node numbers in each subgraph are different.
The data acquisition method is that each acquired unit is assigned with a number and is provided with a sensor, the sensor acquires every deltat, the total number of the acquired units is the total number of nodes in the network, and the data format acquired in the data set is time, number i and number j.
Furthermore, the maximum connected subgraph is formed by abstracting the collected units with face-to-face contact in delta t time in the data collected by each sliding time window into an edge between two nodes, and the network is formed without considering repeated edges, and the data maximum group in the network is the giant branch in the network, namely the maximum connected subgraph.
Preferably, the maximum connected subgraph is calculated and found through a depth-first traversal algorithm or a breadth-first traversal algorithm in a common graph theory.
More preferably, the time interval Δt=20s.
Step 2, a hypergraph conversion step;
In order to facilitate calculation and deduction, the hypergraph network constructed in the hypergraph network construction step needs to be converted into a factor graph in the form of a two-part graph G (V, U, E) formed by a group of non-overlapping variable nodes V (V 1,V2,...,Vn), a group of factor nodes U (E 1、e2...,en) and a group of edge sets E which are interacted pairwise between the variable nodes V and the factor nodes U, wherein the pairwise interaction between each variable node V and the factor nodes U links one non-overlapping variable node to one factor node, the factor graph is associated with the hypergraph through simple mapping, namely, the nodes of the hypergraph network are mapped into a variable node set V of the factor graph, each factor node U in the factor graph corresponds to the hyperedge of the hypergraph network one by one, the main difference between the hypergraph and the conventional graph is that edges are different, the nodes of the conventional graph have strip edges, namely that the two nodes have strip lines, but the nodes contained by the hyperedge are more than or equal to 2, namely, the variable node set V of the hypergraph and the factor node 35 is the same as the abstract node set V, and the factor node U is the abstract node 35, and the abstract node is the abstract node 35.
Step 3, a hypergraph target attack step;
Traversing the degree of each variable node and factor node in the factor graph converted by the hypergraph, thereby obtaining the degree distribution of the variable node and factor node by statistics, obtaining the degree distribution generating function and the redundancy distribution generating function of the variable node and factor node, constructing a function cluster W α(ki which not only comprises the probability influence of the degree of each node on the node to be removed, but also comprises the probability influence of different attack strategies on the node to be removed on the basis of the degree distribution generating function and the redundancy distribution generating function, obtaining the network topology characteristic of the hypergraph network after coping with the target attack by a general method for converting the target attack problem into a random attack problem and a self-consistent equation mathematical tool, and obtaining the theoretical framework of the hypergraph network for carrying out the target attack on the basis of the node hyperdegree according to the network topology characteristic, thereby predicting the occurrence collapse critical value of the hypergraph network.
Specifically, the degree of each variable node and factor node is traversed, specifically, the degree k of the supergraph network model corresponding to all nodes in the factor graph is counted in sequence, and the degree k is the number of the nodes included by the superedge.
Preferably, the function cluster for constructing the target attack based on the degree of the variable nodeWherein, the - + < α < +, then:
When alpha is set to 0, the probability of each node being removed in the target attack is the same and is equivalent to the random attack problem, when alpha is taken to 1, the probability of each node being removed in the target attack is strictly related to the overstep of the node, when alpha is taken to + -infinity, the nodes in the hypergraph network model are strictly removed from large to small according to the overstep in the target attack, and when alpha is taken to-infinity, the nodes in the hypergraph network model are strictly removed from small to large according to the overstep in the target attack.
More preferably, the general method for converting the target attack problem into a random attack problem in the step 3 may be implemented by using various technical schemes for network model test and analysis in the prior art, which may be implemented by adopting a random selection method to simulate a network attack.
More specifically, the self-consistent equation mathematical tool is to construct a random hypergraph network with superdegree and superedge base obeying poisson distribution, and the probability that an edge formed by paired interaction between a variable node and a factor node in a factor graph reaches an superedge is defined asDefining the probability of reaching a variable node belonging to a superside from a factor node of the superside along an edge formed by paired interaction between the factor node and the factor node as s, and according to a theoretical formula of the supergraph network under random attack
And the function value W α(ki of the node overstock calculation assignment step can obtain the self-consistent equation of the equivalent network of the overstock network under the deliberate attack as follows
And
Where p is the proportion of network reservation nodes in the random attack, G eq0 () is the generating function of the equivalent network G eq,As the generating function of the redundancy distribution of the superside base, G eq1 () is the generating function of the redundancy distribution of the equivalent network G eq, R is the sequence parameter of the probability that a node belongs to a superside in the supergraph network, and the deliberate attack problem on the supergraph network based on node superdegree can be mapped into the random attack problem on the supergraph network, so that the deliberate attack problem based on superdegree in the supergraph network is converted into the random attack problem on the network G eq.
More preferably, the network topology characteristics of the hypergraph network after the target attack is handled comprise the value of different parameters of the hypergraph network, the seepage threshold value of the network, the degree distribution change condition of two types of nodes after the attack is implemented, and the like.
Advantageous effects
Compared with the prior art, the invention has the beneficial effects that:
The method of the invention converts the hypergraph network into the factor graph, judges and calculates the scale of the network by changing the probability of removing the nodes in a deliberate attack mode, introduces self-consistent equations in calculation, finally calculates the number of the nodes in the factor graph as the final scale of the network, and compared with the prior random removal of the nodes without intention, the method can make the hypergraph network crash faster, accurately predict critical points of the hypergraph network crash through strict mathematical derivation, and protect some important nodes in the network protection process by understanding the process of deliberate attack implementation.
In addition, the method has a certain compatible effect, an attack strategy is selected according to different values of the setting index alpha, the intentional attack problem can be reduced to a random attack problem through adjusting the parameter=0, logically, when alpha is set to 0, the probability of deleting each node is 1/N, namely the probability of deleting is the same, the probability is equivalent to the random attack problem, when alpha is taken to 1, the probability of deleting each node is strictly related to the size of the exceeding degree (the larger the exceeding degree is, the larger the value of the probability in a formula is, the higher the exceeding degree is, the problem is not easy to see), when alpha is taken to + -infinity, the nodes in the hypergraph network model are strictly removed from the large scale, when alpha is taken to-infinity, the nodes in the hypergraph network model are strictly removed from the small scale to the large scale, the final scale is equal to the value of R in theory, and the network scale and reliability of the hypergraph network after the intentional attack can be predicted.
Drawings
The foregoing and the following detailed description of the invention will become more apparent when read in conjunction with the following drawings in which:
FIG. 1 is a hypergraph network schematic;
FIG. 2 is a schematic diagram of a hypergraph network conversion factor graph;
FIG. 3 is a schematic diagram of the probability line in the self-consistent equation introduction step;
FIG. 4 is a schematic diagram of a target attack implementation step;
FIG. 5 is a schematic diagram of a construction algorithm for randomly generating a hypergraph network in a self-consistent equation introduction step;
FIG. 6 is a schematic diagram of an algorithm for calculating a maximum connected subgraph in the hypergraph network under certain conditions in the self-consistent equation introduction step;
FIG. 7 is a schematic diagram of a deliberate attack flow based on hypergraph network model;
fig. 8 is a simulated three-dimensional diagram of different parameter values for intentional attack based on hypergraph network model.
Detailed Description
The following embodiments are used to further illustrate the technical solution for achieving the object of the present invention, and it should be noted that the technical solution claimed in the present invention includes but is not limited to the following embodiments.
As a specific embodiment of the present invention, as shown in fig. 6, the present embodiment discloses a method for predicting the network size and reliability of a hypergraph network after deliberate attack, which includes the following steps:
And step 1, hypergraph network construction. Collecting data from the known face-to-face contact data sets by using sliding time windows with the time interval delta t, abstracting and constructing a hypergraph network by using nodes among the data, finding out the maximum connected subgraphs in the hypergraph network formed by the data collected by each sliding time window, and constructing a hypergraph network model by aggregating all the maximum connected subgraphs after de-duplication, wherein the aggregation of different connected subgraphs into the hypergraph model is equivalent to the slow formation of a large network, namely the hypergraph, because the node numbers in each subgraph are different.
Furthermore, the face-to-face contact data set is mainly data acquired in the social activity process and comprises data of face-to-face contact of different acquired units in conferences, schools and hospitals, the data acquisition method comprises the steps of wearing a sensor by the acquired units, acquiring each acquired unit once every deltat, distributing a number to each acquired unit before acquisition, wherein the total number of the acquired units is the total number of nodes in a network, and the data format acquired in the data set is time, number i and number j.
Specifically, the maximum connected subgraph is formed by abstracting the collected units, which are in face-to-face contact in Δt time, in the data collected by each sliding time window into an edge between two nodes, so as to form a network, and the maximum group of data is the giant branch in the network, namely the maximum connected subgraph, without considering repeated edges.
Preferably, the maximum connected subgraph is calculated and found by a depth-first traversal algorithm or a breadth-first traversal algorithm in a common graph theory, and more preferably, the time interval Δt=20s.
And step 2, a hypergraph conversion step. For ease of calculation and derivation, as shown in FIGS. 1 and 2, the hypergraph network constructed in the hypergraph network construction step needs to be converted into a network consisting of a set of non-overlapping variable nodes V (V 1,V2,...,Vn), A set of factor nodes U (E 1、e2...,en), and a set of factor graphs in the form of two graphs G (V, U, E) formed by the paired interactions between the variable nodes V and the factor nodes U, wherein the paired interactions between each variable node V and the factor nodes U link a non-overlapping variable node to a factor node, the factor graph is associated with a hypergraph through simple mapping, namely, the nodes of the hypergraph network are mapped into a variable node set V of the factor graph, each factor node U in the factor graph corresponds to the hyperedge of the hypergraph network one by one, the main difference between the hypergraph and the nodes in the conventional graph is that edges are different, namely, a strip line exists between the two nodes, but the hyperedge comprises nodes with the number equal to or greater than 2, for example, the hyperedge E 1 in fig. 1 comprises two variable nodes V 1、V2, and the hyperedge E 5 comprises five variable nodes V 1,V6,V7 and V 8. In fig. 1, there are eight variable nodes V 1～V8 in total, the corresponding factor graph 2 is also eight, the left e 1 super-edge contains two variable nodes V 1、V2, so the corresponding right e 1 is connected with the two variable nodes V 1、V2, that is, the variable node sets v= { V 1,V2,...,Vn } of the super-graph and the factor graph are all identical, the factor node set is denoted by U, and the node e 1、e2...,en in the right graph is actually abstracted. As shown in FIG. 1, the hypergraph network consists of 8 vertexes and 5 hyperedges, wherein the hyperdegree is represented by k, the radix size of the hyperedge is represented by m, then m1＝2,m2＝3,m3＝5,m4＝2,m5＝4,k1＝2;k2＝2;k3＝2;k4＝2;K5＝2;K6＝3;k7＝2;k8＝1, FIG. 2 is a factor graph transformed by the hypergraph network, small circles represent nodes, the size of which is positively correlated with the hyperdegree, polygons represent factor nodes, wherein the small dots represent the radix of the hyperedge as 2, and the number of edges of the polygons represent the number of nodes contained in the corresponding hyperedge.
Step 3, a hypergraph target attack step;
traversing the superdegree k of each node and the number of nodes contained in each superside m in the hypergraph network, and counting the degree distribution P (k) and P (m) of the superdegree k and the superside m. Obtaining the generating function of the degree distribution of the two types of nodes according to the definition of the generating function through the degree distribution of the two types of nodes Generating function of redundancy distribution
The function cluster W α(ki of the target attack is constructed based on the superdegree k of the node). A node overstep calculation assignment step of sequentially counting the degrees k of all nodes in the factor graph corresponding to the overstep network model, wherein the degrees k are the number of edges directly connected with the factor nodes, and a function value W α(ki is allocated to each node i with the degree ki), and considering that the denominator of W α(ki) cannot be 0, therefore,Wherein, the - +_α < α < +_infinity.
To be able to obtain the size of the network after a deliberate attack, a self-consistent equation is introduced, defining the probability of a factor graph from a variable node to an overrun along the edge formed by the paired interactions with a factor node asDefining the probability of reaching a variable node belonging to a superside from an edge formed by the paired interactions between a factor node of the superside and a factor node is defined as s,And s are shown in fig. 3 (a) and (b), respectively, circles represent nodes, polygons represent factor nodes, triangles, squares and pentagons represent factor nodes with the cardinalities of 3, 4 and 5, respectively, and then according to the theoretical formula of the hypergraph network under random attackAnd
According to the function cluster W α(ki of the node overstock assignment step), after removing (1-p) nodes in the overstock network, the self-consistent equation of the overstock network under the deliberate attack can be obtained as follows
And
Where p is the proportion of network reservation nodes in the random attack, G eq0 () is the generating function of the equivalent network G eq,As a generating function of the redundancy distribution of the superside radix, G eq1 () is a generating function of the redundancy distribution of the equivalent network G eq, and R is a sequence parameter of the probability that a node in the supergraph network belongs to the superside. Since the factor nodes have never been deleted all the time, in the self-consistent equation, the generation function on the superbase remains unchanged, but the equivalent generation functions of the superdegree distribution and the redundancy distribution after deliberate attack satisfy G 0 () andThus, the deliberate attack problem on the hypergraph network based on node overstep can be mapped into a random attack problem on the hypergraph network, thereby converting the deliberate attack problem based on overstep in the hypergraph network into a random attack problem on the network G eq, as shown in fig. 4.
The theoretical derivation step is specifically as follows:
Firstly, a random hypergraph network with hyperdegree and hyperedge base obeying poisson distribution is constructed, a specific construction algorithm is shown in fig. 5, wherein an average hyperdegree is defined as k, an average hyperedge base is defined as m, and a theoretical formula of the hypergraph network under random attack is shown as formula (1):
wherein p is the proportion of the network reserved nodes in the random attack, and the seepage problem is described by finding the probability that one node belongs to a giant branch in the hypergraph network as a sequence parameter R.
In the random hypergraph, the order parameter R is expressed as:
Furthermore, the generation function of the hyperdegree distribution of the initial network is defined as
Where P (k) is the oversubstance distribution of the network, and the generation function of the oversubstance distribution is
Average overrun of the network is
Similarly, the generation function of the superbase distribution of the initial network is defined as
Where P (m) is the degree distribution of the superbase of the network, the generation function of the redundancy distribution of the superbase is
The average cardinality of the superside of the network is
The formulae according to (3) - (8), (1) and (2) can be converted into
And
On the premise of not losing generality, generating functions of node overstock distribution in the random overstock network after deliberate attack, then calculating the size of giant branches of the random overstock network after deliberate attack by generating corresponding factor graphs and utilizing self-consistent equations, wherein the main idea is to find the generating functions of an equivalent network G eq of initial network overstock distribution, so that the problem of deliberate attack based on overstock in the overstock network is converted into the problem of random attack on the network G eq, and specifically, each node i with overstock i is required to be allocated with a function value W α(ki):
according to equation (11), after removing (1-P) nodes in the hypergraph network, calculating the degree distribution P p (k) of the remaining nodes, but leaving edges of the remaining nodes leading to the removed nodes;
Let G p (k) be the number of nodes with k degrees,
When another node is deleted, gp (k) becomes
When N is → infinity, equation (13) can be represented by the derivative of Gp (k) with respect to p,
By deriving p in formula (12) and combining with formula (14), it is possible to obtain
This is accurate for N→infinity, in order to solve equation (15), a function is definedAnd introducing a new variableI.e.
Then the solution of formula (15) is
And
This can be demonstrated to satisfy equation (15);
After removing the nodes of the score (1-p) from the network according to (11), the generating function of the nodes remaining in the network is:
because the hypergraph network is randomly connected, the probability that an edge ends at the remaining nodes is equal to the ratio of the number of edges issued from the remaining nodes to the number of edges issued from all nodes of the original network:
where < k > is the average of the initial hypergraph network and the average of the remaining nodes is
Removing edges ending in deleted nodes of the randomly connected network is equivalent to randomly removing remaining nodesA portion of the edges. At this time randomly removeThe generating function of the rest nodes after partial edges is equal to
If a network Geq with a generating function G eq0 is found so that after a random attack that removes part of the nodes (1-p), the generating function of the remaining nodes in Geq is the same as G c (x), then
Geq0(x)≡Gc(1-p+px), (23)
From the formula (23), it is possible to obtain
The generating function of the redundancy distribution is that
Since factor nodes have never been deleted from time to time, in the self-consistent equation, the generation function on the superbase remains unchanged, but the equivalent generation functions of the oversubscription distribution and the redundancy oversubscription distribution after deliberate attack satisfy equations (24) and (25), the deliberate attack problem on the overspray network based on node overspray can be mapped as a random attack problem on the overspray network. From equations (9) and (25), the self-consistent equation of the equivalent network of the hypergraph network under deliberate attack can be obtained as
And
The specific implementation conditions are as follows:
When α=0, then the probability of each node being removed is 1/N, when the simulation is performed in the vs2019 software tool using the c++ language, a vector container with a length of N is first generated, values in the container are respectively 1,2, and when the network removal ratio is p, a random function random is sequentially utilized to select and delete a number in the container, the length of the container is reduced by one, and the nodes with the corresponding numbers in the hypergraph network are removed, and the pN is repeated in total.
When α=1, then the probability of each node being removed is positive correlated with its overstep, and when simulation is performed in the vs2019 software tool using the c++ language, a vector container is first generated, with a length ofThe values in the container are respectively 1, & gt, 1 (k 1 +1 are total), 2, & gt, 2 (k 2 +1 are total), and the values of the values are equal to or equal to N, N, N (k N +1 are total), when the network removal proportion is p, one number i in the container is selected by using a random function random in sequence, all the numbers i in the container are deleted, the length of the container is reduced by (k i +1), and the nodes corresponding to the numbers in the hypergraph network are removed, and the number p is repeated for the total times.
When alpha is positive or negative, the effect is logical, a relatively large number is taken in actual operation, and the method is used for carrying out the same method, and the effect is that the node removal sequence is strict from high to low, because the larger the superdegree is, the larger the proportion occupied in the container is.
Therefore, the relation of the superdegree of each node in the whole supergraph network total node can be obtained, and different deliberate attack strategies are adopted by adjusting the values of the parameters.
A deliberate attack flowchart based on hypergraph network model as shown in fig. 7. Through the deliberate attack method, the hypergraph network can be destroyed better than random attack, the scale of the residual nodes after the attack can be calculated, and a certain prediction effect is achieved.
More specifically, for example, in the VS2019 software, a random hypergraph network with hyperdegree and hyperedge base obeying poisson distribution is constructed through the c++ language. Fig. 8 is a three-dimensional diagram of the case where the method is implemented in a random hypergraph network:
Wherein (a) - (d) are fixed (< k > =3) and < m > =2, 3,4,5 and 6 are set, α is-1, 0, 1 and 2 respectively, it can be seen that the robustness of the network becomes more robust with the increase of < m >, the giant branches of the network become larger, and the robustness of the network becomes weaker with the increase of the α value, the network threshold becomes higher.
(E) The (h) is fixed (< m > =3), and < k > =2, 3, 4,5 and 6 are set, and α is-1, 0,1 and 2, respectively. It can also be seen that the robustness of the network becomes more robust with an increase in < k >, the giant branching type of the network becomes larger, and that the network threshold becomes higher and the robustness of the network becomes weaker with an increase in alpha value.
To further verify the intentional attack scenario of the present invention under a real network, four real world datasets are used:
Contacts in workplace (workplace) the data set contains a temporal network of contacts between individuals measured in an office building in france on days 24, 6, and 24, 7, and 3 of 2013. The nodes are employees of the company. Wearable sensors are used to build a close-range contact network from person to person. Contacts are aggregated in a 20 second time window. Each superside is the largest clique in each layer (i.e., each interval) of the time-contact network.
Primary school time network data (primary school) this data set contains a time network of contacts between children and teachers used in studies published in BMC infectious disease 2014, 14:695. The nodes are students of primary school. Wearable sensors are used to build a close-range contact network between students. Contacts are aggregated in a 20 second time window. Each superside is the largest clique in each layer (i.e., each interval) of the time-contact network.
High school contact and friendship network (high school) these data sets correspond to the contact and friendship relationships between the high school students, france mosaic 12, 2013, measured by several techniques. The node is a student at a senior citizen. Wearable sensors are used to build a close-range contact network between students. Contacts are aggregated in a 20 second time window. Each superside is the largest clique in each layer (i.e., each interval) of the time-contact network.
SFHH conference data set (conference) that describes the face-to-face interactions of 405 participants of the SFHH conference held in france, 2009 (6 months 4 to 5 days 2009). The nodes are participants of the conference. Wearable sensors are used to build a close-range contact network from person to person. Contacts aggregate within a time window of 20 seconds. Each superside is the largest clique in each layer (i.e., each interval) of the time-contact network.
The method provides an analysis framework for analyzing robustness of the random hypergraph with overstock distribution and superedge base obeying arbitrary overstock distribution under intentional attack, and discovers giant branches and seepage threshold values of a single-layer random hypergraph network. In addition, when the superdegree and the cardinality of the superside in the supergraph network obey poisson distribution, and the expected values of the superdegree and the cardinality of the superside are fixed, the average degree of the whole network can be obtained by the product of the two expected values, so the method further analyzes the influence of the average degree in the supergraph network on the robustness of the system, and finds that the average degree has a certain influence on the robustness of the network, namely when < k > or < m > is fixed, the robustness of the system is enhanced along with the increase of the average degree, and when the average degree is unchanged, the greater the < k >, the more the system is robust. Also, when < k > and < m > are fixed, the robustness of the hypergraph network becomes more fragile as the alpha value increases. Experiments are carried out on a hypergraph network and a real network, wherein the hypergraph network and the hyperedge base are respectively subjected to poisson distribution, the hypergraph network and the real network are respectively subjected to power law distribution, and the effectiveness of the equations under different topological structures is verified.
Claims (6)
1. A method for predicting the network size and reliability of a hypergraph network after a deliberate attack, comprising the steps of:
Step 1, hypergraph network construction
Collecting data from the known face-to-face contact data sets by using sliding event windows with the time interval delta t, abstracting and constructing a hypergraph network by using nodes among the data, finding out the maximum connected subgraphs in the hypergraph network formed by the data collected by each sliding time window, and aggregating all the maximum connected subgraphs after de-duplication to construct a hypergraph network model;
The method for collecting the data in the face-to-face contact data sets comprises the steps of distributing a number for each collected unit and wearing a sensor, wherein the sensor collects every deltat, the total number of the collected units is the total number of nodes in a network, and the data formats collected in the data sets are time, number i and number j;
step 2, hypergraph transformation step
Converting the hypergraph network constructed in the hypergraph network construction step into a factor graph formed by a group of non-overlapping variable nodes V (V 1,V2,…,Vn), a group of factor nodes U (E 1,e2,…,en) and a group of two graphs G (V, U, E) formed by a pair-wise interaction between the variable nodes V and the factor nodes U, wherein the pair-wise interaction between each variable node V and the factor nodes U links one non-overlapping variable node to one factor node, the nodes of the hypergraph network are mapped into a variable node set V of the factor graph, and each factor node U in the factor graph corresponds to the hyperedge of the hypergraph network one by one;
Step 3, hypergraph target attack step
Traversing the degree of each variable node and factor node degree of degree exceeding in the factor graph converted by the hypergraph, thereby counting to obtain the degree distribution of the variable node and the factor node, obtaining the degree distribution generating function and the redundancy distribution generating function of the variable node and the factor node, constructing a function cluster W α(ki which not only comprises the probability influence of the degree of each node on the node to be removed but also comprises the target attack of different attack strategies on the probability influence of the node to be removed on the node on the basis of the degree distribution generating function and the redundancy distribution generating function, obtaining the network topology characteristic of the hypergraph network after coping with the target attack by a general method for converting the target attack problem into a random attack problem and a self-consistent equation mathematical tool, and obtaining the theoretical framework of the hypergraph network for carrying out the target attack on the basis of the node degree exceeding according to the network topology characteristic;
The self-consistent equation data tool is used for constructing a random hypergraph network with superdegree and superside base obeying poisson distribution, wherein the probability that an edge formed by paired interaction between a variable node and a factor node in a factor graph reaches a superside is defined as s, and the probability that an edge formed by paired interaction between the factor node and the factor node reaches a variable node belonging to the superside is defined as s according to the theoretical formula of the hypergraph network under random attack: And the function value W α(ki of the node overstock assignment step), the self-consistent equation of the equivalent network of the overstock network under the deliberate attack can be obtained as follows: A kind of electronic device ,
Wherein p is the proportion of the reserved nodes in the network in the random attack, G eq0 () is the generating function of the equivalent network Geq, G eq1 () is the generating function of the redundancy distribution of the over-edge base number, G eq, R is the sequence parameter of the probability that one node belongs to the over-edge in the over-graph network, and the deliberate attack problem on the over-graph network based on the node overstep can be mapped into the random attack problem on the over-graph network, thereby converting the deliberate attack problem based on the overstep into the random attack problem on the network G eq in the over-graph network.
2. The method of predicting network scale and reliability after deliberate attack of hypergraph network of claim 1, wherein the maximum connected subgraph is a network formed by abstracting collected units with face-to-face contact in Δt time in data collected by each sliding time window into an edge between two nodes, and the data maximum group in the network is giant branches in the network, namely the maximum connected subgraph.
3. The method for predicting the network scale and reliability of the hypergraph network after deliberate attack according to claim 1 or 2, wherein the maximum connected subgraph is calculated and found by a depth-first traversal algorithm or a breadth-first traversal algorithm.
4. A method of predicting network size and reliability of a hypergraph network after a deliberate attack according to claim 1 or 2, wherein the time interval Δt = 20s.
5. The method for predicting network scale and reliability of hypergraph network after deliberate attack of claim 1, wherein in step 3, the degree of traversing each variable node and factor node is specifically counted in turn, wherein hyperk is the number of nodes included by the hyperedge.
6. A method for predicting network scale and reliability of hypergraph network after intentional attack according to claim 1 or 5, wherein the function clusterThe method comprises the steps of setting alpha to be 0, enabling the probability of each node to be removed in a target attack to be identical, and enabling the probability of each node to be removed in the target attack to be identical to the random attack problem, wherein when alpha is 1, the probability of each node to be removed in the target attack is strictly related to the degree of superdegree, when alpha is +infinity, the nodes in the supergraph network model are strictly removed from large to small in the target attack, and when alpha is +infinity, the nodes in the supergraph network model are strictly removed from small to large in the target attack.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210087042.8A CN114444699B (en) | 2022-01-25 | 2022-01-25 | Method for predicting the network size and reliability of hypergraph networks after deliberate attacks |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210087042.8A CN114444699B (en) | 2022-01-25 | 2022-01-25 | Method for predicting the network size and reliability of hypergraph networks after deliberate attacks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114444699A CN114444699A (en) | 2022-05-06 |
| CN114444699B true CN114444699B (en) | 2025-09-02 |
Family
ID=81370290
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210087042.8A Active CN114444699B (en) | 2022-01-25 | 2022-01-25 | Method for predicting the network size and reliability of hypergraph networks after deliberate attacks |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114444699B (en) |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2015184221A1 (en) * | 2014-05-30 | 2015-12-03 | Georgetown University | A process and framework for facilitating information sharing using a distributed hypergraph |
| CN113705085B (en) * | 2021-08-03 | 2023-01-17 | 国家电网有限公司信息通信分公司 | Intelligent power grid multi-level structure modeling and risk assessment method |
| CN117997643A (en) * | 2024-03-13 | 2024-05-07 | 浙江师范大学 | Method and system for predicting robustness of multi-layer high-order interaction network |
-
2022
- 2022-01-25 CN CN202210087042.8A patent/CN114444699B/en active Active
Non-Patent Citations (1)
| Title |
|---|
| Disintegrate hypergraph networks by attacking hyperedge;Hao Peng 等;《Journal of King Saud University-Computer and Information Sciences》;20220628;第34卷(第7期);4679-4685 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114444699A (en) | 2022-05-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111932386B (en) | User account determining method and device, information pushing method and device, and electronic equipment | |
| CN112580217A (en) | Communication system structure parameterization modeling method based on complex network | |
| CN106127590A (en) | A kind of information Situation Awareness based on node power of influence and propagation management and control model | |
| Shang et al. | Epidemic spreading on complex networks with overlapping and non-overlapping community structure | |
| CN113807520A (en) | Knowledge graph alignment model training method based on graph neural network | |
| CN114676292B (en) | Super-network high-influence node ordering method | |
| CN116055333B (en) | Network key group identification method based on high-order structure | |
| CN106327345A (en) | Social group discovering method based on multi-network modularity | |
| Hsiao | Evaluating the mobilization effect of online political network structures: a comparison between the Black lives matter network and ideal type network configurations | |
| CN115796229A (en) | Graph node embedding method, system, device and storage medium | |
| CN117272195A (en) | Block chain abnormal node detection method and system based on graph convolution attention network | |
| CN119030743A (en) | An anomaly detection method integrating knowledge distillation and group learning | |
| CN114628041B (en) | A method and system for identifying key nodes based on closeness centrality calculation | |
| CN114444699B (en) | Method for predicting the network size and reliability of hypergraph networks after deliberate attacks | |
| CN113420628B (en) | A group behavior identification method, device, computer equipment and storage medium | |
| Liu et al. | Uniformly bound-growing network models and their spanning trees | |
| Li | Construction of International Sports Communication Influence Model Based on Data Mining | |
| CN117034134B (en) | Propagation source positioning method based on encoder and decoder framework | |
| CN118194976A (en) | An adaptive federated learning method and system based on heterogeneous edge devices | |
| CN115331833A (en) | Multilayer network, construction method thereof and infectious disease modeling simulation method | |
| CN116614859A (en) | A method and system for identifying key nodes in an Ad Hoc network | |
| Wang et al. | Horizontal Federated Heterogeneous Graph Learning: A Multi-Scale Adaptive Solution to Data Distribution Challenges | |
| CN112199563A (en) | A Graph Height Node Detection and Classification Method Based on Triangle Detection | |
| Li et al. | Critical Nodes Identification Algorithm Based on ResNet-CBAM | |
| Dai et al. | Detection of influential nodes using neighbor closeness in complex networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant |