CN114513426B - CCN community division method based on node similarity and influence - Google Patents
CCN community division method based on node similarity and influence Download PDFInfo
- Publication number
- CN114513426B CN114513426B CN202210198386.6A CN202210198386A CN114513426B CN 114513426 B CN114513426 B CN 114513426B CN 202210198386 A CN202210198386 A CN 202210198386A CN 114513426 B CN114513426 B CN 114513426B
- Authority
- CN
- China
- Prior art keywords
- node
- community
- value
- centrality
- 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
- 238000000034 method Methods 0.000 title claims abstract description 36
- 239000013598 vector Substances 0.000 claims abstract description 46
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 40
- 238000004891 communication Methods 0.000 claims description 23
- 238000004364 calculation method Methods 0.000 claims description 12
- 230000005540 biological transmission Effects 0.000 claims description 10
- 239000011159 matrix material Substances 0.000 claims description 9
- 238000000638 solvent extraction Methods 0.000 claims description 8
- 238000005265 energy consumption Methods 0.000 claims description 5
- 238000013459 approach Methods 0.000 claims description 4
- 230000000694 effects Effects 0.000 claims description 4
- 230000003993 interaction Effects 0.000 claims description 3
- 238000012545 processing Methods 0.000 claims description 3
- 238000010606 normalization Methods 0.000 claims 1
- 230000008569 process Effects 0.000 abstract description 6
- 235000008694 Humulus lupulus Nutrition 0.000 description 4
- 238000004088 simulation Methods 0.000 description 4
- 238000011161 development Methods 0.000 description 3
- 238000002474 experimental method Methods 0.000 description 3
- 230000008859 change Effects 0.000 description 2
- 230000001419 dependent effect Effects 0.000 description 2
- 238000013507 mapping Methods 0.000 description 2
- 230000007246 mechanism Effects 0.000 description 2
- 238000012546 transfer Methods 0.000 description 2
- 230000007423 decrease Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000004069 differentiation Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/12—Discovery or management of network topologies
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/08—Configuration management of networks or network elements
- H04L41/0803—Configuration setting
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/14—Network analysis or design
- H04L41/142—Network analysis or design using statistical or mathematical methods
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Pure & Applied Mathematics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention provides a CCN community division method based on node similarity and influence, which comprises the following steps: firstly, calculating the centrality of the feature vectors corresponding to all nodes in the community to obtain a standardized value of the centrality of the feature vectors; improving a tag propagation algorithm, and determining an updating rule of a tag propagation value; dividing the CCN network into a plurality of non-overlapping communities based on the standardized feature vector centrality and an improved label propagation algorithm; finally, an SDN controller is deployed in each divided community to help manage the communities. The invention solves the problems of low-efficiency redundancy in the content retrieval process of the existing content center network and the technical problems of poor stability, lack of consideration of similarity between nodes and importance of the nodes in the existing CCN community division method, and can accelerate the speed of content retrieval and route distribution and improve the performance of CCN routing by introducing SDN controllers and community division.
Description
Technical Field
The invention relates to the technical field of network community division, in particular to a CCN community division method based on node similarity and influence.
Background
Traditional network architecture based on TCP/IP cannot well support the increasing network traffic demand, and users often do not know the content provider when requesting the content, so that the problem that the destination address cannot be embedded into the interest packet for forwarding is caused. The content-centric network (CCN) is converted from a provider-driven end-to-end communication mode to an interest-driven content retrieval communication mode, which makes CCN unable to route by adopting a hop-by-hop return method according to source and destination IP addresses like TCP/IP, so that the design of an efficient CCN routing scheme will be a problem to be solved urgently by CCN network architecture. In recent years, CCN routing mechanisms have been widely studied, and there are two more effective schemes for solving the problems of scalability and large-scale deployment of CCNs. One is in combination with a Software Defined Network (SDN) because SDN, as a unique model of the future internet, enables separation of the control plane from the data plane; another approach is to make community division, but when community division is made, the size and content of the community are difficult to determine, which creates new challenges for community division.
Scholars have proposed many community discovery algorithms, girvan et al have proposed an edge-betweenness-based split GN algorithm, deleting the edge with the largest edge betweenness each time until all edges are removed; blondel et al propose a modularity maximized louvain algorithm, where each point is considered as an independent community, and the edge weights between communities and within communities after community folding are calculated until finally combined into one community. Raghavan et al propose a Label Propagation Algorithm (LPA) that has linear time complexity compared to the first two algorithms, and is suitable for community partitioning in large networks.
The core idea of the LPA algorithm is: first, each node in the way is assigned a label value to represent the community in which the node is located. Finding out a node with the largest label propagation value (when the maximum value is not the same, randomly selecting one) in the neighbor nodes, adding the node into the community, updating the label propagation value of the node, and stopping iteration when the label propagation value of the node is not changed; otherwise repeating the steps.
In the conventional LPA algorithm, the determination of the initial tag value has randomness, so that the divided communities have the defects of poor stability and low accuracy, and many scholars have improved the LPA algorithm in order to further solve the problem. Luo et al improve community division quality by optimizing objective functions, but suffer from poor LPA stability; the method comprises the steps that the label updating sequence is changed by calculating the importance of the label, but the similarity between nodes is not considered; song et al change the tag update sequence by calculating node similarity, but does not consider the importance of the node.
Disclosure of Invention
Aiming at the problems of low-efficiency redundancy in the content retrieval process of the existing content center network and the technical problems of poor stability, lack of consideration of similarity among nodes and importance of the nodes in the existing CCN community division method, the invention provides the CCN community division method based on node similarity and influence, which can accelerate the speed of content retrieval and route distribution and improve the performance of CCN routing by introducing an SDN controller and community division.
In order to solve the technical problems, the invention adopts the following technical scheme: a CCN community division method based on node similarity and influence comprises the following steps:
step one: calculating the centrality of the feature vectors corresponding to all nodes in the community, and normalizing the centrality of the feature vectors to obtain n normalized values of the centrality of the feature vectors;
step two: inputting the obtained value of the centrality of the standardized feature vector into a tag propagation algorithm to be used as an initial value of a tag propagation value, and determining an updating rule of the tag propagation value based on the interest similarity and the social influence among nodes in the community;
step three: dividing the CCN network into a plurality of non-overlapping communities based on the standardized feature vector centrality and an improved label propagation algorithm;
step four: and selecting one node with the greatest competitiveness in each divided community to deploy the SDN controller so as to help manage community information and topology structures and interactions with other communities.
The calculation method of the feature vector centrality corresponding to each node in the community comprises the following steps: with a= (e ij ) n×n Representing the adjacency matrix corresponding to the undirected graph, x= (X) 1 ,x 2 ,…,x n ) A feature vector representing the adjacency matrix for any node v i Corresponding feature vector value x i The method comprises the following steps:
wherein: i is more than or equal to 1 and less than or equal to n, n represents the total number of nodes, and x j Representing node v i Is a neighbor node v of (1) j Corresponding toThe eigenvalue, lambda is the eigenvalue corresponding to the eigenvector X of the adjacency matrix a; when the characteristic vector value x is i Performing multiple iterations, when the value reaches a steady state, the characteristic vector value x i Representing node v i The corresponding feature vector centrality.
Center x of feature vector in interval (0, 1) i Normalizing to obtain n normalized values of the centrality of the feature vectors i '：
The method for calculating the interest similarity between the nodes comprises the following steps: suppose node v i With neighbor node v j The same number of interest fields is p, node v i With neighbor node v j The interest similarity between the two is:
wherein ,respectively represent node v i 、v j For the interest field f k Interest weights of (a);
when node v i Generating a field containing interest f k When requested, there are:
the calculation formula of the social influence among the nodes is as follows:
k i ＝|Γ(i)|，k j ＝|Γ(j)| (6)
in the formula ：dij For flowing through node v i With neighbor node v j Γ (i) and Γ (j) are respectively the node v i With neighbor node v j Is set of (k) i And k is equal to j Respectively node v i With neighbor node v j Is (i, j) is node v i With neighbor node v j Euclidean distance between them.
The updating rule for determining the tag propagation value in the second step is as follows:
w ij ＝αTw ij +(1-α)Sw ij (8)
in the formula ：Ni For node v i Is a neighbor node v of (1) j Is set in la j Is a neighbor node v j Tag activity value, k j Is a neighbor node v j Degree, w of ij For node v i With neighbor node v j Similarity of interest Tw between ij And social influence Sw ij Alpha is a corresponding constant coefficient reflecting the similarity of interest Tw between nodes ij And social influence Sw ij The weight occupied.
The non-overlapping community dividing method in the third step comprises the following steps: firstly, determining the number of communities divided and the value x of centrality of n normalized eigenvectors i ' descending order is carried out, and nodes corresponding to the first k values are selected as corresponding initial communities, so that k initial communities are obtained; other nodes are then developed as their community members in a parallel fashion based on a hierarchical traversal approach for the k initial communities.
The calculation formula of the node competitiveness in each community in the fourth step is as follows:
in the formula ：Dfxi For node v i Data forwarding capability of Co xi Is SDN controller S x Deployment in community C x Node v of (2) i At the cost of the communication in question,for adjusting the coefficients.
The data forwarding capability of the node is related to the label propagation value and the network bandwidth after the node is standardized, wherein:
the label propagation value after node standardization is:
the network bandwidth after node standardization is:
in the formula ：Lk Representing node v k Tag propagation value, b xi Representing node v x And node v i Transmission bandwidth between b xk Representing node v x And node v k Transmission bandwidth between them;
the data forwarding capability of the node is:
Df xi ＝β·L i ′+(1-β)·Bw i ′ (12)
where β is the tag propagation value and the weight occupied by the network bandwidth.
The calculation formula of the communication cost of the node is as follows:
Co xi ＝Nu i ·Cs i +Tf i ·Ec i (13)
in the formula ：Nui Representing node v i Cs is the number of requests of (2) i Representing node v i Fixed delay consumption, tf i Representing flow through node v i Data flow, ec i Representing the energy consumption of processing each bit of data;
the communication cost is standardized, and values are distributed among intervals (0, 1), so that the standardized communication cost is as follows:
in the formula ：Coxk Representing node v x And node v i Cost of communication between.
According to the invention, a SDN controller and community division are introduced to study a CCN routing mechanism, and a CCN network is divided into a plurality of communities by combining two main methods of feature vector centrality and label propagation; then, a node is selected to deploy SDN controllers in the community according to node competitiveness, which is mainly dependent on data forwarding capability of the node and communication cost of the community, wherein each SDN controller consists of SIT and SCT for recording of network information and topology management. In addition, the network topology is simulated based on a real data set, and experimental results show that the method has good performance.
Drawings
In order to more clearly illustrate the embodiments of the invention or the technical solutions in the prior art, the drawings that are required in the embodiments or the description of the prior art will be briefly described, it being obvious that the drawings in the following description are only some embodiments of the invention, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.
FIG. 1 is a flow chart of the present invention;
FIG. 2 is a pseudo code algorithm of community partitioning according to the present invention;
FIG. 3 is a pseudo code algorithm of SDN controller deployment node selection of the present invention;
FIG. 4 is a graph showing the variation of module values corresponding to different Lim values when the social division is performed;
FIG. 5 is a graph of average route hops for four different algorithms, SI-LPA, S-LPA, LPAh and HPI_LPA, for different number of interest requests;
FIG. 6 is a graph showing average cache hit rates for four different algorithms, SI-LPA, S-LPA, LPAh and HPI_LPA, for different request times of interest.
Detailed Description
The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without any inventive effort, are intended to be within the scope of the invention.
As shown in FIG. 1, the invention provides a CCN community division method based on node similarity and influence, wherein the value of the characteristic vector centrality of a node is used as an initial value of a label propagation value in a label propagation algorithm; secondly, comprehensively considering the similarity and influence between the nodes and the neighbor nodes to provide a method for updating the tag propagation value, and dividing the CCN network topology structure into a plurality of non-overlapping communities; and finally, selecting the node with the greatest competitiveness on each divided community to deploy the SDN controller so as to help better manage community functions and perform inter-community routing. Experiments show that introducing SDN controllers and community division can accelerate CCN content retrieval and route distribution, thereby improving CCN routing performance.
The method specifically comprises the following steps:
step one: firstly, calculating the centrality of feature vectors corresponding to nodes in a community, wherein A= (e) ij ) n×n Representing the adjacency matrix corresponding to the undirected graph, x= (X) 1 ,x 2 ,…,x n ) A feature vector representing the adjacency matrix for any node v i Corresponding feature vector value x i The method comprises the following steps:
wherein: n represents the total number of nodes, x j Representing node v i Is a neighbor node v of (1) j Corresponding featuresThe vector value lambda is the eigenvalue corresponding to the eigenvector X of the adjacency matrix A.
Using the above formula, when the characteristic vector value x is calculated i Performing multiple iterations, when the value reaches a steady state, the characteristic vector value x at the moment i I.e. representing node v i The centrality of the corresponding feature vectors. For ease of calculation, the feature vector centrality x is within the interval (0, 1) i Normalizing to obtain n normalized values of the centrality of the feature vectors i '：
Step two: improving a tag propagation algorithm: the value x of the centrality of the normalized feature vector to be obtained i The' input tag propagation algorithm is used as an initial value of the tag propagation value. And then determining an updating rule of the label propagation value based on the interest similarity and the social influence among the nodes in the community, namely further solving the latest label propagation value of the node according to the determined updating rule of the label propagation value.
The interest similarity between the nodes is the Tanimoto coefficient correlation corresponding to the interest weight set of the same interest field in the interest sets of the two nodes. The interest similarity calculation method between the nodes comprises the following steps: suppose node v i With neighbor node v j The same number of interest fields is p, node v i With neighbor node v j The interest similarity between the two is:
wherein ,respectively represent node v i 、v j For the interest field f k Is a weight of interest of (1).
The interest weight represents the historical request times of the node to an interest field byRepresenting node v i For the interest field f k When node v is the interest weight of i Generating a field containing interest f k When requested, there are:
the social influence among the nodes is reflected by the social distance between the two nodes. The social distance between nodes is proportional to the data traffic through the two nodes, inversely proportional to the distance between the two nodes, and related to the degree of the nodes. The calculation formula of the social influence among the nodes is as follows:
k i ＝|Γ(i)|，k j ＝|Γ(j)| (6)
in the formula ：dij For flowing through node v i With neighbor node v j Γ (i) and Γ (j) are respectively the node v i With neighbor node v j Is set of (k) i And k is equal to j Respectively node v i With neighbor node v j Is (i, j) is node v i With neighbor node v j Euclidean distance between them.
According to the interest similarity and social influence among nodes in the community, the updating rule for determining the tag propagation value is as follows:
w ij ＝αTw ij +(1-α)Sw ij (8)
in the formula ：Ni For node v i Is a neighbor node v of (1) j Is set in la j Is a neighbor node v j Tag activity value of (2)，k j Is a neighbor node v j Degree, w of ij For node v i With neighbor node v j Similarity of interest Tw between ij And social influence Sw ij Alpha is a corresponding constant coefficient reflecting the similarity of interest Tw between nodes ij And social influence Sw ij The weight occupied.
Step three: the CCN network is partitioned into several non-overlapping communities based on the normalized feature vector centrality and the improved tag propagation algorithm. Community C x The community members cannot develop without limitation, so that some limitation conditions are needed when making community decisions, so as to determine the number of communities to be divided and the number of nodes contained in each community.
The specific method comprises the following steps: firstly, determining the number of communities to be divided, and obtaining the value x of the centrality of n standardized feature vectors in the step one i ' descending order, selecting the nodes corresponding to the first k values as corresponding initial communities to obtain k initial communities, and using C 1 ，C 2 ，…，C k A representation; other nodes are then developed as members of their communities in a parallel fashion based on a hierarchical traversal approach for the k initial communities. In the process of traversing community division hierarchy, if newly traversed node v to be added in two communities i And v j Is adjacent node, i.e. node v i And v j Directly connecting the two communities, and combining the two communities into one community; if there are eta nodes v to be added i And v j In the case of neighboring nodes, the number of communities finally divided is k- η=p.
Secondly, the problem of the number of the members in the communities is solved, and the number of the members in each divided community is limited, namely the number of the nodes is limited. Firstly, giving an upper limit Lim of the number of members in a community, and in the hierarchical traversal process, if the number of nodes in the community exceeds the upper limit value, no new nodes are added into the community, and member development of the community is terminated. That is, during the development of community members, a node will be contended by different communities, and thisThe final attribution right of the node is determined according to the label propagation values of the node in different communities, because the same node can have different label propagation values due to the difference of corresponding communities in the hierarchical traversal process of the node. Suppose node v i From communities C respectively x and Cy Performing hierarchical traversal if node v i Slave community C x Traversing tags have greater propagation values than slave community C y Traversing tag propagation values, and community C x If the number of members does not reach the upper limit value, node v i Subject to community C x Continuing community C x Member development of (a); otherwise if community C y The number of members does not reach the upper limit, node v i Subject to community C y 。
The web communities partitioned based on feature vector centrality and improved tag propagation algorithms are non-overlapping, and the number of communities that are ultimately partitioned is known. According to the description, a pseudo code algorithm of community division is shown in fig. 2, namely, a standardized value of feature vector centrality is used as an initial tag propagation value, the first k communities are selected as initial communities, and the k communities are updated with the tag propagation values.
Step four: and selecting one node with the greatest competitiveness in each divided community to deploy the SDN controller so as to help manage community information and topology structures and interactions with other communities.
Deployment of SDN controllers is on a per community C basis x The competition of the medium nodes is determined, and SDN controllers are distributed to the community C by researching the aspects of data forwarding capacity, communication cost and the like of the nodes x On the node with the greatest internal competitiveness. For community C x With Cp xi Representing nodes v in a community i The competition of (2) is:
in the formula ：Dfxi For node v i Data forwarding capability of Co xi Is SDN controller S x Deployed atCommunity C x Node v of (2) i At the cost of the communication in question,is a suitable adjustment factor. It is known that the competitiveness of a node is proportional to the data forwarding capability of the node and inversely proportional to the communication cost of the node.
The data forwarding capability of the node is related to the label propagation value and the network bandwidth after the node is standardized, wherein:
the label propagation value after node standardization is:
the network bandwidth after node standardization is:
in the formula ：Lk Representing node v k Tag propagation value, b xi Representing node v x And node v i Transmission bandwidth between b xk Representing node v x And node v k Transmission bandwidth therebetween.
The data forwarding capability of the node is:
Df xi ＝β•L i ′+(1-β)·Bw i ′ (12)
where β is the tag propagation value and the weight occupied by the network bandwidth.
The node v i The communication cost of the router can be expressed by two aspects of transmission delay and energy consumption of the router, wherein the transmission delay and the transmission delay are respectively controlled by a node v i Number of requests Nu i And node v i Fixed latency consumption Cs i Related to; energy consumption and flow through node v i Data flow Tf of (a) i And energy consumption Ec for processing data per bit i The calculation formula of the communication cost is as follows:
Co xi ＝Nu i •Cs i +Tf i ·Ec i (13)
the communication cost is standardized, and values are distributed among intervals (0, 1), so that the standardized communication cost is as follows:
in the formula ：Coxk Representing node v x And node v i Cost of communication between.
According to the above description, SDN controller deployment node v i The pseudo code algorithm selected by (2) is shown in fig. 3, namely, the node with the largest competitiveness is calculated according to the data forwarding capability and the communication cost between the nodes in the community, and the controller is deployed on the node.
In order to enable SDN controllers to effectively manage community contents, content retrieval speed is improved, an information index table (SIT) is designed for each SDN controller, and the SIT is used for recording the mapping of nodes where the contents in the community are located and providing support for routing in the community; and a community topology table (SCT) for helping to maintain community topology information and to perform inter-community routing.
An information index table (SIT) consists of three fields: content name Prefix (PRE), content name (CAN), content Holder (CHL). The method has the main effects that the mapping of the content on each node in the community is established on the SDN controller, so that the SDN controller can clearly grasp the content holding condition of community members and can accurately forward the content to a requester. A node in a community may store multiple different contents (but not multiple times for the same content), and the same content may also be held by multiple different nodes.
The topology table (SCT) consists of three fields, namely an Adjacent Community (ACS), a content name Prefix (PRE) and a content transfer Number (NCT). Wherein, adjacent Communities (ACS) refer to which communities are adjacent to the current community; content name Prefix (PRE) refers to a prefix tag that transmits content between two communities; the Number of Content Transfers (NCT) refers to the number of times data is transferred in total between two communities. The main function is to record the total times of transmission of different types of contents between communities and provide support for route inquiry of subsequent interest packets between communities.
In the invention, ndnSIM is adopted to perform data simulation and performance analysis, and an artificial synthetic network topology structure consisting of 100 points and 474 edges is generated, wherein 98 points are router nodes, and 2 points are server nodes. In the initial state, all data content stores are only stored on the server node, and the router node does not store the content. The community division comparison algorithm adopted in the experiment is LPAh, HPI-LPL, S-LPA and the like, and the ant colony algorithm is uniformly adopted to carry out CCN data routing. Multiple simulation experiments were performed on the Windows system of Intel (R) Core (TM) i7-9700 CPU@3.00GHz CPU, 32 GBRAM. By carrying out 100 experiments on each division algorithm, the average route hop count and the cache hit rate of each community division algorithm are calculated under different interest request times.
Simulation environment and parameter setting: by performing simulation experiments under different parameter settings, a specific numerical value is determined, so that the whole routing decision can achieve optimal performance. The determination of the upper limit Lim parameter of the number of members in the community among all the parameters is absolutely critical, and the slight performance of the route is directly affected. All parameters and values related to the invention are shown in table 1 below:
TABLE 1 parameter value settings
In order to evaluate the quality of the community division result, the concept of modularity Q is introduced to measure the quality of the community division, and the closer the value is to 1, the better the community division quality is proved, but the modularity is difficult to reach 1 under normal conditions. The corresponding module value changes for different Lim values when social differentiation is performed are shown in fig. 4. A peak in the image was observed, especially when lim=20, with a modularity closest to 1. It can also be seen from fig. 4 that the change in the modularity value increases rapidly before the peak is reached, and the modularity decreases gradually after the peak is reached. This illustrates that the build process of strong modularity is fast, but the disruption is relatively slow.
The result is shown in fig. 5 by observing the average number of route hops at different times of interest requests. As can be seen from the data in fig. 6: (1) with the increase of the interest request times, the average route hop count of the SI-LPA algorithm is obviously lower than that of the S-LPA algorithm, the LPAh algorithm and the HPI_LPA algorithm, because the SI-LPA algorithm introduces the SDN controller to manage communities, with the increase of the request times, the probability of requesting the same content again is increased, at the moment, the content can be directly acquired in communities according to the SDN controller, and the route hop count is reduced to a certain extent; and the SI-LPA algorithm comprehensively uses the interest similarity and social influence of the nodes to divide communities, so that the community structure divided each time tends to be stable. (2) The number of route hops of SI-LPA, S-LPA and HPI-LPA algorithms eventually tend to be stable, but the number of route hops of LPAh algorithms is always in a fluctuating state, because the LPAh algorithms optimize community division quality by using an objective function, but do not solve the problem of poor stability.
The cache hit rate in the community is observed under different interest request times by requesting the same content for different nodes in the community, and the result is shown in fig. 6. As can be seen from fig. 6, as the number of requests increases, the cache hit rate of each partitioning policy increases, but the SI-LPA algorithm has the highest cache hit rate, because the management function of the SDN controller provides better support for caching of community contents of the SI-LPA algorithm policy, so that the requests in the community are changed to large contents with higher priority, thereby increasing the cache hit rate.
According to the invention, the SDN controller and community division are introduced to study the CCN route, and the CCN network topology is divided into a plurality of communities by combining two main methods of feature vector centrality and label propagation; then, a node is selected to deploy SDN controllers in the community according to node competitiveness, which is mainly dependent on data forwarding capability of the node and communication cost of the community, wherein each SDN controller consists of SIT and SCT for recording of network information and topology management. In addition, the network topology is simulated based on the real data set, and experimental results show that the scheme has good performance.
The foregoing description of the preferred embodiments of the invention is not intended to be limiting, but rather is intended to cover all modifications, equivalents, alternatives, and improvements that fall within the spirit and scope of the invention.
Claims (5)
1. The CCN community division method based on node similarity and influence is characterized by comprising the following steps of:
step one: calculating the centrality of the feature vectors corresponding to all nodes in the community, and normalizing the centrality of the feature vectors to obtain n normalized values of the centrality of the feature vectors;
the calculation method of the feature vector centrality corresponding to each node in the community comprises the following steps: with a= (e ij ) n×n Representing the adjacency matrix corresponding to the undirected graph, x= (X) 1 ,x 2 ,…,x n ) A feature vector representing the adjacency matrix for any node v i Corresponding feature vector value x i The method comprises the following steps:
wherein: i is more than or equal to 1 and less than or equal to n, n represents the total number of nodes, and x j Representing node v i Is a neighbor node v of (1) j The corresponding eigenvalue, lambda is the eigenvalue corresponding to eigenvector X of the adjacent matrix A; when the characteristic vector value x is i Performing multiple iterations, when the value reaches a steady state, the characteristic vector value x i Representing node v i The centrality of the corresponding feature vectors;
step two: inputting the obtained value of the centrality of the standardized feature vector into a tag propagation algorithm to be used as an initial value of a tag propagation value, and determining an updating rule of the tag propagation value based on the interest similarity and the social influence among nodes in the community;
the sectionThe method for calculating the interest similarity between the points comprises the following steps: suppose node v i With neighbor node v j The same number of interest fields is p, node v i With neighbor node v j The interest similarity between the two is:
wherein ,respectively represent node v i 、v j For the interest field f k Interest weights of (a);
when node v i Generating a field containing interest f k When requested, there are:
the calculation formula of the social influence among the nodes is as follows:
k i ＝|Γ(i)|，k j ＝|Γ(j)|
in the formula ：dij For flowing through node v i With neighbor node v j Γ (i) and Γ (j) are respectively the node v i With neighbor node v j Is set of (k) i And k is equal to j Respectively node v i With neighbor node v j Is (i, j) is node v i With neighbor node v j Euclidean distance between them;
the updating rule for determining the tag propagation value in the second step is as follows:
w ij ＝αTw ij +(1-α)Sw ij
in the formula ：Ni For node v i Is a neighbor node v of (1) j Is set in la j Is a neighbor node v j Tag activity value, k j Is a neighbor node v j Degree, w of ij For node v i With neighbor node v j Similarity of interest Tw between ij And social influence Sw ij α is a constant coefficient;
step three: dividing the CCN network into a plurality of non-overlapping communities based on the standardized feature vector centrality and an improved label propagation algorithm;
step four: selecting one node with the greatest competitiveness in each divided community to deploy an SDN controller so as to help manage community information, topological structures and interactions with other communities;
the calculation formula of the node competitiveness in each community in the fourth step is as follows:
in the formula ：Dfxi For node v i Data forwarding capability of Co xi Is SDN controller S x Deployment in community C x Node v of (2) i At the cost of the communication in question,for adjusting the coefficients.
2. The CCN community partitioning method based on node similarity and influence as claimed in claim 1, wherein the feature vector centrality x is within the interval (0, 1) i Normalizing to obtain n normalized values of the centrality of the feature vectors i '：
3. The CCN community partitioning method based on node similarity and influence according to claim 1 or 2, wherein the non-overlapping community partitioning method in the third step is as follows: firstly, determining the number of communities divided and the value x of centrality of n normalized eigenvectors i ' descending order is carried out, and nodes corresponding to the first k values are selected as corresponding initial communities, so that k initial communities are obtained; other nodes are then developed as their community members in a parallel fashion based on a hierarchical traversal approach for the k initial communities.
4. The CCN community partitioning method based on node similarity and impact of claim 1, wherein the data forwarding capability of the node is related to label propagation value and network bandwidth after node normalization, wherein:
the label propagation value after node standardization is:
the network bandwidth after node standardization is:
in the formula ：Lk Representing node v k Tag propagation value, b xi Representing node v x And node v i Transmission bandwidth between b xk Representing node v x And node v k Transmission bandwidth between them;
the data forwarding capability of the node is:
Df xi ＝β·L i ′+(1-β)·Bw i ′
where β is the tag propagation value and the weight occupied by the network bandwidth.
5. The CCN community partitioning method based on node similarity and influence as claimed in claim 1 or 4, wherein the calculation formula of the communication cost of the node is:
Co xi ＝Nu i ·Cs i +Tf i ·Ec i
in the formula ：Nui Representing node v i Cs is the number of requests of (2) i Representing node v i Fixed delay consumption, tf i Representing flow through node v i Data flow, ec i Representing the energy consumption of processing each bit of data;
the communication cost is standardized, and values are distributed among intervals (0, 1), so that the standardized communication cost is as follows:
in the formula ：Coxk Representing node v x And node v i Cost of communication between.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210198386.6A CN114513426B (en) | 2022-03-02 | 2022-03-02 | CCN community division method based on node similarity and influence |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210198386.6A CN114513426B (en) | 2022-03-02 | 2022-03-02 | CCN community division method based on node similarity and influence |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114513426A CN114513426A (en) | 2022-05-17 |
| CN114513426B true CN114513426B (en) | 2023-09-15 |
Family
ID=81553821
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210198386.6A Active CN114513426B (en) | 2022-03-02 | 2022-03-02 | CCN community division method based on node similarity and influence |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114513426B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115797871A (en) * | 2022-12-22 | 2023-03-14 | 廊坊师范学院 | Analysis method and system for infant companion social network |
| CN116132310B (en) * | 2023-02-17 | 2023-10-20 | 西安电子科技大学广州研究院 | Large-scale software defined network performance prediction method |
Citations (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7023979B1 (en) * | 2002-03-07 | 2006-04-04 | Wai Wu | Telephony control system with intelligent call routing |
| JP2014157502A (en) * | 2013-02-15 | 2014-08-28 | Dainippon Printing Co Ltd | Server device, program and communication system |
| CN106888163A (en) * | 2017-03-31 | 2017-06-23 | 中国科学技术大学苏州研究院 | The method for routing divided based on network domains in software defined network |
| CN106886524A (en) * | 2015-12-15 | 2017-06-23 | 天津科技大学 | A kind of community network community division method based on random walk |
| CN107194818A (en) * | 2017-04-13 | 2017-09-22 | 天津科技大学 | Label based on pitch point importance propagates community discovery algorithm |
| CN107862617A (en) * | 2017-10-20 | 2018-03-30 | 江苏大学 | A kind of microblogging community division method based on user's comprehensive similarity |
| CN108073944A (en) * | 2017-10-18 | 2018-05-25 | 南京邮电大学 | A kind of label based on local influence power propagates community discovery method |
| CN108595684A (en) * | 2018-05-04 | 2018-09-28 | 中南大学 | A kind of overlapping community discovery method and system based on preferential learning mechanism |
| CN109067588A (en) * | 2018-08-21 | 2018-12-21 | 电子科技大学 | A kind of semi-supervised non-overlap community discovery method based on partial tag information |
| CN110909173A (en) * | 2019-11-13 | 2020-03-24 | 河海大学 | Non-overlapping community discovery method based on label propagation |
| CN111159577A (en) * | 2019-12-31 | 2020-05-15 | 北京明略软件系统有限公司 | Community division method and device, storage medium and electronic device |
| CN113254999A (en) * | 2021-06-04 | 2021-08-13 | 郑州轻工业大学 | User community mining method and system based on differential privacy |
| WO2021189729A1 (en) * | 2020-03-27 | 2021-09-30 | 深圳壹账通智能科技有限公司 | Information analysis method, apparatus and device for complex relationship network, and storage medium |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP3380946A4 (en) * | 2015-11-25 | 2019-05-01 | Fliri, Anton Franz, Joseph | Method and descriptors for comparing object-induced information flows in a plurality of interaction networks |
| US10394829B2 (en) * | 2015-12-08 | 2019-08-27 | International Business Machines Corporation | Content authoring |
| CN107153713B (en) * | 2017-05-27 | 2018-02-23 | 合肥工业大学 | Overlapping community detection method and system based on similitude between node in social networks |
-
2022
- 2022-03-02 CN CN202210198386.6A patent/CN114513426B/en active Active
Patent Citations (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7023979B1 (en) * | 2002-03-07 | 2006-04-04 | Wai Wu | Telephony control system with intelligent call routing |
| JP2014157502A (en) * | 2013-02-15 | 2014-08-28 | Dainippon Printing Co Ltd | Server device, program and communication system |
| CN106886524A (en) * | 2015-12-15 | 2017-06-23 | 天津科技大学 | A kind of community network community division method based on random walk |
| CN106888163A (en) * | 2017-03-31 | 2017-06-23 | 中国科学技术大学苏州研究院 | The method for routing divided based on network domains in software defined network |
| CN107194818A (en) * | 2017-04-13 | 2017-09-22 | 天津科技大学 | Label based on pitch point importance propagates community discovery algorithm |
| CN108073944A (en) * | 2017-10-18 | 2018-05-25 | 南京邮电大学 | A kind of label based on local influence power propagates community discovery method |
| CN107862617A (en) * | 2017-10-20 | 2018-03-30 | 江苏大学 | A kind of microblogging community division method based on user's comprehensive similarity |
| CN108595684A (en) * | 2018-05-04 | 2018-09-28 | 中南大学 | A kind of overlapping community discovery method and system based on preferential learning mechanism |
| CN109067588A (en) * | 2018-08-21 | 2018-12-21 | 电子科技大学 | A kind of semi-supervised non-overlap community discovery method based on partial tag information |
| CN110909173A (en) * | 2019-11-13 | 2020-03-24 | 河海大学 | Non-overlapping community discovery method based on label propagation |
| CN111159577A (en) * | 2019-12-31 | 2020-05-15 | 北京明略软件系统有限公司 | Community division method and device, storage medium and electronic device |
| WO2021189729A1 (en) * | 2020-03-27 | 2021-09-30 | 深圳壹账通智能科技有限公司 | Information analysis method, apparatus and device for complex relationship network, and storage medium |
| CN113254999A (en) * | 2021-06-04 | 2021-08-13 | 郑州轻工业大学 | User community mining method and system based on differential privacy |
Non-Patent Citations (7)
| Title |
|---|
| A Node Influence Based Label Propagation Algorithm for Community Detection in Networks;Yan Xing ect.;《The Scientific World Journal》;全文 * |
| Label propagation method based on bi-objective optimization for ambiguous community detection in large networks;Junhai Luo , Lei Ye;《Scientific RepoRts 》;全文 * |
| TNS-LPA: An Improved Label Propagation Algorithm for Community Detection Based on Two-Level Neighbourhood Similarity;Guiqiong Xu ect.;《IEEE Access ( Volume: 9)》;全文 * |
| 基于残差神经网络的心脏病预测系统的设计与实现;蔡增玉，崔梦梦，侯佳林，张建伟;《现代电子技术》;全文 * |
| 基于节点综合相似度的多标签传播社区划分算法;郝梓琳;李雷;施化吉;;计算机应用研究(06);全文 * |
| 基于随机游走相似度矩阵的改进标签传播算法;宋琛;张贤坤;费松;荚佳;刘栋;;计算机应用与软件(08);全文 * |
| 融合特征向量中心性与标签熵的标签传播算法;潘曙灿;许青林;;计算机工程与科学(08);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114513426A (en) | 2022-05-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3665460B2 (en) | Route selection system, method, and recording medium by response time tuning of distributed autonomous cooperation type | |
| CN104753797B (en) | A kind of content center network dynamic routing method based on selectivity caching | |
| Ioannidis et al. | Adaptive caching networks with optimality guarantees | |
| CN114513426B (en) | CCN community division method based on node similarity and influence | |
| CN104717304B (en) | A kind of CDN P2P content optimizations select system | |
| JP6190288B2 (en) | Cache control apparatus, method, and program | |
| Hou et al. | Bloom-filter-based request node collaboration caching for named data networking | |
| Wu et al. | MBP: A max-benefit probability-based caching strategy in information-centric networking | |
| Shan et al. | Proactive caching placement for arbitrary topology with multi-hop forwarding in ICN | |
| CN113472420B (en) | Satellite network cache placement method based on regional user interest perception | |
| Gui et al. | A cache placement strategy based on entropy weighting method and TOPSIS in named data networking | |
| Zhang et al. | NCPP-based caching and NUR-based resource allocation for information-centric networking | |
| CN111294394A (en) | Adaptive caching strategy based on complex network intersection point | |
| CN115473854B (en) | Intelligent flow control method for multi-mode network | |
| EP3193490B1 (en) | Method and system for distributed optimal caching of content over a network | |
| Yao et al. | A SMDP-based forwarding scheme in named data networking | |
| Fan et al. | Popularity and gain based caching scheme for information-centric networks | |
| Tabei et al. | Design of multi-armed bandit-based routing for in-network caching | |
| Delvadia et al. | CCJRF-ICN: A novel mechanism for coadjuvant caching joint request forwarding in information centric networks | |
| Phoha et al. | Faster Web page allocation with neural networks | |
| Ben-Ammar et al. | A versatile Markov chain model for the performance analysis of CCN caching systems | |
| CN107302571B (en) | The routing of information centre's network and buffer memory management method based on drosophila algorithm | |
| Mahananda et al. | Performance of homogeneous and heterogeneous cache policy for named data network | |
| CN108512685B (en) | Information center network flow control method and device | |
| Guangmin | An improved Kademlia routing algorithm for P2P network |
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 | ||
| GR01 | Patent grant |