Privacy Protection Method for Sensitive Weighted Edges in Social Networks

( Weihua Gong ),( Rong Jin ),( Yanjun Li ),( Lianghuai Yang ),( Jianping Mei ) 한국인터넷정보학회 2021 KSII Transactions on Internet and Information Syst Vol.15 No.2

Privacy vulnerability of social networks is one of the major concerns for social science research and business analysis. Most existing studies which mainly focus on un-weighted network graph, have designed various privacy models similar to k-anonymity to prevent data disclosure of vertex attributes or relationships, but they may be suffered from serious problems of huge information loss and significant modification of key properties of the network structure. Furthermore, there still lacks further considerations of privacy protection for important sensitive edges in weighted social networks. To address this problem, this paper proposes a privacy preserving method to protect sensitive weighted edges. Firstly, the sensitive edges are differentiated from weighted edges according to the edge betweenness centrality, which evaluates the importance of entities in social network. Then, the perturbation operations are used to preserve the privacy of weighted social network by adding some pseudo-edges or modifying specific edge weights, so that the bottleneck problem of information flow can be well resolved in key area of the social network. Experimental results show that the proposed method can not only effectively preserve the sensitive edges with lower computation cost, but also maintain the stability of the network structures. Further, the capability of defending against malicious attacks to important sensitive edges has been greatly improved.

Edge-Based Motion Vector Processing for Frame Interpolation Based on Weighted Vector Median Filter

PARK, Ju Hyun,KIM, Young-Chul,HOON, Hong-Sung The Institute of Electronics, Information and Comm 2010 IEICE transactions on information and systems Vol.93 No.11

<P>In this paper, we propose a new motion vector smoothing algorithm using weighted vector median filtering based on edge direction for frame interpolation. The proposed WVM (Weighted Vector Median) system adjusts the weighting values based on edge direction, which is derived from spatial coherence between the edge direction continuity of a moving object and motion vector (MV) reliability. The edge based weighting scheme removes the effect of outliers and irregular MVs from the MV smoothing process. Simulation results show that the proposed algorithm can correct wrong motion vectors and thus improve both the subjective and objective visual quality compared with conventional methods.</P>

A NEW VERTEX-COLORING EDGE-WEIGHTING OF COMPLETE GRAPHS

Farahani, Mohammad Reza The Korean Society for Computational and Applied M 2014 Journal of applied mathematics & informatics Vol.32 No.1

Let G = (V ; E) be a simple undirected graph without loops and multiple edges, the vertex and edge sets of it are represented by V = V (G) and E = E(G), respectively. A weighting w of the edges of a graph G induces a coloring of the vertices of G where the color of vertex v, denoted $S_v:={\Sigma}_{e{\ni}v}\;w(e)$. A k-edge-weighting of a graph G is an assignment of an integer weight, w(e) ${\in}${1,2,...,k} to each edge e, such that two vertex-color $S_v$, $S_u$ be distinct for every edge uv. In this paper we determine an exact 3-edge-weighting of complete graphs $k_{3q+1}\;{\forall}_q\;{\in}\;{\mathbb{N}}$. Several open questions are also included.

A New Vertex-Coloring Edge-Weighting of Complete Graphs

Mohammad Reza Farahani 한국전산응용수학회 2014 Journal of applied mathematics & informatics Vol.32 No.1

Let G = (V E) be a simple undirected graph without loops and multiple edges, the vertex and edge sets of it are represented by V = V (G) and E = E(G), respectively. A weighting w of the edges of a graph G induces a coloring of the vertices of G where the color of vertex v, denoted Sv := Σ e∋v w(e). A k-edge-weighting of a graph G is an assignment of an integer weight, w(e) ∈{1, 2, ..., k} to each edge e, such that two vertex- color Sv Su be distinct for every edge uv. In this paper we determine an exact 3-edge-weighting of complete graphs k3q+1 ∀q ∈ N. Several open questions are also included.

한 사이클 내에서 최대 가중치 간선을 제거하기 위한 최소 신장트리 알고리즘

최명복,한태용,이상운 한국인터넷방송통신학회 2014 한국인터넷방송통신학회 논문지 Vol.14 No.2

본 논문은 최소신장트리를 쉽고 빠르게 구하는 방법을 제안하였다. 제안된 알고리즘은 먼저, 그래프의 가중치 간선의 수를 축소시키는 방법으로 그래프를 단순화 시켰다. 간선 수를 축소시키는 방법으로는 그래프 정점의 결합가가 3 이상인 경우, 최대 가중치 간선을 제거하는 방법을 적용하였다. 다음으로, 그래프를 단순화 시킨 축소된 모집단 간선 들을 대상으로 사이클이 발생하는 부분을 확인하여 사이클 발생 간선들 중에서 최대 가중치를 갖는 간선을 삭제하는 방법을 적용하였다. 다양한 9개 그래프에 대해 제안된 사이클 최대 가중치 간선 제거 알고리즘을 적용한 결과 그래프 의 사이클 개수만큼만 수행하여 MST를 쉽게 구하는 장점을 보였다. 모집단 축소 기법을 적용한 결과, 9개 그래프의 사이클 개수를 66%로 감소시키는 결과를 얻었으며, 최소 2개에서 최대 8개의 사이클에서의 최대 가중치 간선만 삭제 하면 MST를 얻는 효과를 얻었다. This paper suggests a method that obtains the minimum spanning tree (MST) far more easily and rapidly than the present ones. The suggested algorithm, firstly, simplifies a graph by means of reducing the number of edges of the graph. To achieve this, it applies a method of eliminating the maximum weight edge if the valency of vertices of the graph is equal to or more than 3. As a result of this step, we can obtain the reduced edge population. Next, it applies a method in which the maximum weight edge is eliminated within the cycle. On applying the suggested population minimizing and maximum weight edge deletion algorithms to 9 various graphs, as many as the number of cycles of the graph is executed and MST is easily obtained. It turns out to lessen 66% of the number of cycles and obtain the MST in at least 2 and at most 8 cycles by only deleting the maximum weight edges.

선택-삭제 최소신장트리 알고리즘

최명복,이상운 한국인터넷방송통신학회 2013 한국인터넷방송통신학회 논문지 Vol.13 No.4

본 논문은 알고리즘 수행 횟수를 줄여 최소신장트리를 빨리 얻는 방법을 제안하였다. 제안된 알고리즘은 선 택과 삭제 과정을 수행한다. 선택 과정은 먼저, 그래프의 모든 정점들에 대해 Borůvka의 첫 번째 단계를 수행하고, 특정 정점들에 대해 Borůvka의 첫 번째 단계를 재 수행하여 간선들의 모집단을 축소시키는 결과를 얻었다. 삭제 과 정은 축소된 모집단 간선들에 대해 3개 정점들 간에 사이클이 발생할 경우 최대 가중치 간선을 삭제한다. 나머지 간 선들 중 최대 가중치 간선에 대해 결합가 개념을 적용하여 삭제한다. 마지막으로 결합가가 큰 정점들 간의 사이클이 발생하는 경우 최대 가중치 간선을 삭제하는 기법을 적용하였다. 선택-삭제 알고리즘을 9개의 다양한 그래프에 적용 하여 알고리즘 적용성을 평가하였다. 제안된 선택 과정은 MST 알고리즘을 최적으로 수행해야 하는 간선의 수와 비 교시 6개는 적은 개수를, 3개 그래프만이 1개 큰 간선을 선택하는 결과를 나타내어 최적으로 간선을 선택하는 방법임 을 알 수 있다. 삭제 단계를 Kruskal 알고리즘을 적용할 경우 Kruskal 알고리즘을 최적으로 수행하는 횟수와 비교한 결과 6개의 그래프는 수행 횟수가 적은 반면, 3개 그래프는 1회 많게 수행하는 결과를 얻었다. 또한, 제안된 삭제 단 계를 수행할 경우 1개 그래프는 1단계만, 5개 그래프는 2단계까지, 나머지 3개 그래프만이 3단계를 수행하는 결과를 나타내었다. 결국, 선택-삭제 알고리즘이 MST 알고리즘들 중에서 가장 적은 수행 횟수를 나타내었다. This algorithm suggests a method in which a minimum spanning tree can be obtained fast by reducing the number of an algorithm execution. The suggested algorithm performs a select-and-delete process. In the select process, firstly, it performs Borůvka’s first stage for all the vertices of a graph. Then it re-performs Borůvka’s first stage for specific vertices and reduces the population of the edges. In the delete process, it deletes the maximum weight edge if any cycle occurs between the 3 edges of the edges with the reduced population. After, among the remaining edges, applying the valency concept, it gets rid of maximum weight edges. Finally, it eliminates the maximum weight edges if a cycle happens among the vertices with a big valency. The select-and-delete algorithm was applied to 9 various graphs and was evaluated its applicability. The suggested select process is believed to be the vest way to choose the edges, since it showed that it chose less number of big edges from 6 graphs, and only from 3 graphs, comparing to the number of edges that is to be performed when using MST algorithm. When applied the delete process to Kruskal algorithm, the number of performances by Kruskal was less in 6 graphs, but 1 more in each 3 graph. Also, when using the suggested delete process, 1 graph performed only the 1st stage, 5 graphs till 2nd stage, and the remaining till 3rd stage. Finally, the select-and-delete algorithm showed its least number of performances among the MST algorithms.

2-간선 연결 그래프를 사용한 최소신장트리 알고리즘 제안

이상운 한국인터넷방송통신학회 2014 한국인터넷방송통신학회 논문지 Vol.14 No.4

본 논문은 원 그래프를 2-간선 연결 그래프로 단순화하고, 사이클 속성을 적용하여 최소신장트리를 빠르게 얻는 알고리즘을 제안하였다. Borůvka 알고리즘은 정점 당 최소 가중치 간선 을 1개씩 선택하는 1-간선 연결 그래프에 대해 사이클 속성을 적용하여 부분신장트리를 얻는다. 추가적으로 절단속성을 적용하여 부분신장트리를 연결하는 최소 가중치 간선을 선택한다. Kruskal 알고리즘은 그래프의 모든 간선을 대상으로 오름차순으로 절단 속성을 적용한다. 역-삭제 알고리즘은 내림차순으로 사이클 속성을 적용한다. Borůvka, Kruskal과 역-삭제 알고리즘은 모든 간선들을 대상으로 하기 때문에 항상 회 수행된다. 제안된 알고리즘은 첫 번째로, 정점 당 최소 가중치 간선을 2개씩 선택하는 2-간선 연결 그래프를 얻는다. 두 번째로, 2-간선 연결 그래프에 대해 사이클 속성을 적용하여 일 때 알고리즘을 종료시켰다. 제안된 방법들을 10개의 실제 그래프들에 적용한 결과 모두 최소신장트리를 얻는데 성공하였다. 또한, Borůvka, Kruskal과 역-삭제 알고리즘에 비해 수행 횟수를 60% 단축시켰다. This paper suggests a fast minimum spanning tree algorithm which simplify the original graph to 2-edge connected graph, and using the cycling property. Borůvka algorithm firstly gets the partial spanning tree using cycle property for one-edge connected graph that selects the only one minimum weighted edge per vertex . Additionally, that selects minimum weighted edge between partial spanning trees using cut property. Kruskal algorithm uses cut property for ascending ordered of all edges. Reverse-delete algorithm uses cycle property for descending ordered of all edges. Borůvka and Kruskal algorithms always perform times for all edges. The proposed algorithm obtains 2-edge connected graph that selects 2 minimum weighted edges for each vertex firstly. Secondly, we use cycle property for 2-edges connected graph, and stop the algorithm until For actual 10 benchmark data, The proposed algorithm can be get the minimum spanning trees. Also, this algorithm reduces 60% of the trial number than Borůvka, Kruskal and Reverse-delete algorithms.

입지선정 범위 예측을 위한 신경망 기반의 엣지 가중치 예측

고정륜(JeongRyun Ko),전현주(Hyeon-Ju Jeon),전승훈(Joshua. Jeon),윤정섭(Jeong-seop Yoon),정재은(Jason J. Jung),김봉길(Bonggil Kim) 한국정보통신학회 2021 한국정보통신학회 종합학술대회 논문집 Vol.25 No.1

본 논문은 노드와 엣지로 이루어진 그래프 구성을 통해 신경망을 활용하여 엣지 가중치 예측 방안을 제안하고자 한다. 사회 구성요소 중 하나인 브랜드들의 중요도 높은 전략 중 출점전략에 대해 초점을 맞추어 보았다. 본 논문에서는 1) 브랜드 지점들을 노드로 구성하고, 지점 간 관계를 엣지로 구성한다. 그리고 지점 간 실제 도보 및 주행 가능 거릿값을 엣지 가중치로 표현한 그래프를 구성한다. 그리고 2)엣지를 수치화하여 신경망을 학습해 엣지의 가중치인 지점 간 거릿값을 예측하는 방안을 제안한다. 제안한 방식을 활용함으로 예측되는 특정 브랜드의 출점 범위를 성공적인 브랜드의 출점전략 분석할 시에 활용할 수 있을 것으로 예상한다. This paper is a proposal for edge weight prediction using neural networks to graph configurations of nodes and edges. Brand is one of the components of society. and one of the brand's most important strategies is geographical location strategy. This paper is focus on that strategy. In This paper propose two things: 1) Graph Configuration. node consists of brand store, edge consists of store-to-store relationships and edge weight consists of actual walk and drive distance values. 2) numbering edges and training neural networks to predict next store distance values. It is expected to be useful in analyzing successful brand geographical location strategies.

Image Restoration using Weighted Octagonal Median Filter

Eun-Kyung Lee,Cheol-Hun Na 한국정보통신학회 2021 2016 INTERNATIONAL CONFERENCE Vol.12 No.1

One of the most important tasks in image processing is noise filtering. Noise removal in image is a difficult task due to many reasons such as nonstationary sequences and corrupted by various types of noise. Human’s visual perception is heavily based on the edge information. Thus, noise filtering must preserve edges. To remove the noise, we usually use the square-shaped median filter. They possess mathematical simplicity but have the disadvantages that blur the edges. In this paper we consider a new technique for image restoration using a weighted octagonal median filter. This technique consists of simple hypothesis test for edge detection, and we use the weighted octagonal-shaped moving window. The new technique is applied to noise corrupted image and experimental results are compared to the results of the square-shaped median filter and the cross-shaped median filter.

Intensity-guided edge-preserving depth upsampling through weighted L₀ gradient minimization

Jung, Cheolkon,Yu, Shengtao,Kim, Joongkyu Elsevier 2017 Journal of visual communication and image represen Vol.42 No.-

<P><B>Abstract</B></P> <P>Depth is an important visual cue to perceive real-world scenes. Although a time-of-flight (ToF) depth camera can provide depth information in dynamic scenes, captured depth images are often noisy and of low resolution. In this paper, we propose an intensity-guided edge-preserving depth upsampling method through weighted L<SUB>0</SUB> gradient minimization to enhance both resolution and visual quality of depth images. Guided by the high-resolution intensity image, we perform optimization to preserve boundaries of objects. We apply L<SUB>0</SUB> gradient to the regularization term, and compute its weight from both intensity and depth images. We optimize the objective function using alternating minimization and half-quadratic splitting. Experimental results on Middlebury 2005, 2014, and real-world scene datasets demonstrate that the proposed method produces boundary-preserving depth upsampling results and outperforms state-of-the-art ones in terms of accuracy.</P> <P><B>Highlights</B></P> <P> <UL> <LI> Intensity-guided edge-preserving depth upsampling. </LI> <LI> Weighted L<SUB>0</SUB> gradient minimization. </LI> <LI> Alternating minimization and half-quadratic splitting. </LI> <LI> Suppressing edge blurring and texture copying artifacts. </LI> </UL> </P> <P><B>Graphical abstract</B></P> <P>[DISPLAY OMISSION]</P>