( ) Nebulas Rank (In-and-Out Degree) Wilbur

Size: px

Start display at page:

Download "( ) Nebulas Rank (In-and-Out Degree) Wilbur"

연희 길
6 years ago
Views:

1 : Nebulas Rank Nebulas v1.0.1

2 ( ) Nebulas Rank (In-and-Out Degree) Wilbur Core Nebulas Rank ( ) ( ) Core Nebulas Rank ? Core Nebulas Rank Extended Nebulas Rank Extended Nebulas Rank Extended Nebulas Rank A B

3 1., (DApp). (Openness).,,.,. TTP Cookie.,.,.,.,,..,.,.,,.,.. :...,... 1

4 Nebulas Rank., Nebulas Rank.. (,, ).,.,. Nebulas Rank Nebulas Rank, Coinmarketcap.com. Nebulas Rank ( 0.84), Nebulas Rank. Nebulas, Nebulas Rank ( ). Nebulas Rank Nebulas Rank Core Nebulas Rank Extended Nebulas Rank. Core Nebulas Rank.. Extented Nebulas Rank Core Nebulas Rank,., Core Nebulas Rank Extented Nebulas Rank. Nebulas Rank, Nebulas Rank,, Nebulas Rank Nebulas Rank. :, Nebulas Rank Nebulas ( ) ( v1.0.2)[3]. ( ). 2

5 Satoshi Nakamoto,.., 3.,., (Namecoin)[5] (DNS), Open Assets (Colored coins),. (Turing-Complete),.. (Ethereum) [7]. (Smart Contracts),.. (Ethereum Virtual Machine, EVM) EVM., (DApp). DApp,,,., (Killer Dapps)., (Externally owned account, EOA)., Chris Skinner (Value Web), (Value Ecosystem) (Value Exchanges) (Value Stores) 3

6 (Value Management Systems),. Chris. 2.2,.,.,,. PageRank [9]. Google PageRank., PageRank,, PageRank. PageRank Fleder, Kester, Pilai [10], PageRank. PageRank PageRank. Web 2.0 PageRank., PageRank, PageRank LeaderRank. PageRank, LeaderRank. LeaderRank ( ). PageRank (Sybil Attack). LeaderRank (, ),,.,. Nebulas Rank NEM, [17] (Proof of Work) (Proof of Stake) NEM (Proof of Importance), NCDawareRank[14]. NCDawareRank ( ) SCAN[15] [16] [17].,. 2.3 ( ) Nebulas Rank,. Hopcroft [18], PageRank 4

7 . Zhang, ( ) [19]. PageRank (Symmetric Network) [20][12]. : (out-degree),. 3.,. 4.,. Nebulas Core Nebulas Rank,. 5

8 3. Core Nebulas Rank. ( ) Core Nebulas Rank !. L U (L, U)!!. : L = (A, D, T)! (1) A D T!,!,! ( ). (tetrad) : D = {a d, a A, d R*}! (2) T = {(s, t, w, τ)}! (3) a! d a d d s, t, w τ! (!., 0 )!.!!,,. : u dom a. u U, a A! (4) 6

9 : A(u ) = { a A : u dom a}! (5) :! (6) ,. [21],. u 1, u 2 U : A(u 1 ) A(u 2 ) = ϕ Nebulas Rank.,. (Velocity Factor)... : Nebulas ( )[3].., :. R.S Kroszner 6 2,795, [22].,. [23], V!. : M V = P Y! (7) 7

10 ! M V P,!,!!,, (,!.) (GDP). (7). M Y 1 p! Nebulas (Nebulas NAS 4 % ), 2100.!., (7) : V (M + Δm) (s,t,w,τ) T w! (8) M = P Y Δm!.!, (New Keynesian Models)..,.. (, ),!!.. Y!, GDP,.,.,. (8)!. Y! : P Y P Y Y = C(a)! (9) a A C(a) a!!, Core Nebulas Rank. Nebulas.,. ( : Nebulas Proof of Devotion ) 8

11 ( ).. 9

12 4 Nebulas Rank Core Nebulas Rank... : Core Nebulas Rank. [t 0 T, t 0 ]! : Θ(t 0 ) = {(s, t, w, τ) t 0 T τ t 0 w > 0 s t}! (10) Θ(t o ) d c τ!,,!!,!,!. a A C(a) Θ(t o )!!! Core Nebulas Rank : C(a) = Ω(β(a)) Ψ(γ(a)) β(a) a γ(a)! (11)!!!.. s : Nebulas ( )[3] Core Nebulas Rank : 1.!. 2. LeaderRank.,.., PageRank ( : LeaderRank) [20] K 4.1 β(a) [t 0 T, t o ] n, : B i B i+ 1 a A B o, B 1,, B n. : 10

13 d a o, d a 1,, d a n : d a (0), d a (1),, d a (n) d(i) a < d (i+ a 1),0 i n 1 β(a)!,! : (a) = ( d a (k) for n =2 k, k =1, 2, 3,... (d a (k) + da (k+1))/2 for n =2 k +1,k =1, 2, 3,... (12).,. w = 10, =2 v 1 v 2 w = 100, =1 w = 100, =5 w = 10, =3 H(v) ={(v, v1, 100, 1), (v1, v2, 10, 2), (v2, v3, 10, 3), (v3,v,10, 4)} v v 3 w = 10, =4.1: v 1 v 2 w = 100, =5 w = 90, =1 11 v v 3

14 !!! 4.2 (In-and-Out Degree).2:.1. (in-and-out)... : v H(v) H(v) {(v, v 1, w 1, τ 1 ), (v 1, v 2, w 2, τ 2 ),, (v i, v i+ 1, w i, τ i ),, (v n, v, w n+ 1, τ n+ 1 )},!! 1 i n: τ 1 τ i+ 1 (v 1, v 2, 100, 5) n.1,,..! : H 1 (v 1 ), H 2 (v 2 ),, H n (v n ) H i (v i ) (s i m, t i m, w i m, τ i m)!!, H i (v i ) w i m H i (v i )!!,! 0 : (s i, t i, w i, τ i ) T : w i w i m E((s, t, w, ),w m )= (s, t, w wm, ) if w 6= w m if w = w m Θ (t 0 ) = Θ(t 0 ) H i (v) {E(t), t H i (v i )} i = 1,2,, n! (13).2.1 ( ). 12

15 v!! p(v) :! p(v) = w (14) i (s i,v,w i,τ i ) Θ (t 0 ) v! : v,!! γ(v)! q(v) = w (15) i (v,t i,w i,τ i ) Θ (t 0 ) : q(v) arctan! p(v) ) (16) G(v) = (p(v) + q(v)) e 2 sin2 ( π G(v) =(p(v)+q(v)) e 2sin2 ( 4 arctan q(v) p(v) ) q(v) p(v) 4.3: 13

16 γ(v) = ( θ G(v) G(v) + μ )λ! (17)! θ, μ, λ 4.3 Wilbur. Core Nebulas Rank. Nebulas Rank. Core Nebulas Rank f (x), Wilbur 1. Core Nebulas Rank,,. x 1 x 2 f (x) : x f (x 1 + x 2 ) > f (x 1 ) + f (x 2 ) x 1 > 0,x 2 > 0 (18) f(x) =x f(x) =x/(1 + e a+b x ) Nebulas Rank Nebulas Rank Factor.4: Nebulas x 1 x lim f (x 1 + x 2 ) = f (x 1 ) + f (x 2 ) x 1 > 0,x 2 > 0 x 1,x 2 (19) 1 (Sybil Attack) 1970 TV (Sybi)l. Dr. Cornelia Wilbur. Wilbur. 14

17 .,...4. f (x) = x /(1 + e a+ b x ) a > 1,b < 0 (20) A., (11) : C(v) = β(v) 1 + e γ(v) a+ b β(v) 1 + e c+ d γ(v) (21).5: Nebulas Rank Market Capitalization of Ethereum (USD) Nebulas Rank ETH Market Cap Time (day) Core a, b, c, d. Core Nebulas Rank. Nebulas ( : ) ETH ( ) [24]..5 ETH Core Nebulas Rank ETH ( ) (21) Core Nebulas Rank. 15

18 Core Nebulas Rank. p < , (p ). (11) Core Nebulas Rank. 16

19 5 Core Nebulas Rank ( ) Core Nebulas Rank Nebulas Rank ,,. 5.1 (21).., 0 β o. γ.,. β,.,,.,, (21)..,. (Cycle-removal Algorithm). γ = 2β o C =.. (1 + e a+ b β 0)(1 + e c+ 2d β 0).. 2β 2 0. C = γ 2T β o T 2T β0 2. (1 + e a+ b β o)(1 + e ec + c c d β o ), 17

20 5.2 ( ) Sybil Attack P2P [25]. P2P. P2P. ID., ID. P2P (Redundancy),, ID. P2P ID ID ID. ID. ID. P2P. [26].... Core Nebulas Rank.. β o,. N N β = N γ K β K = 2 N 5.1,,. : C = N K β2 0 N (1 + e a+ b β 0 N )(1 + e c+ K d β 0) = Kβ 2 0 (1 + e a+ b β 0 N )(1 + e c+ K d β 0) (22) Core Nebulas Rank Core Nebulas Rank Core Nebulas Rank. 6.1? Core Nebulas Rank.. Nebulas Rank. 18

21 Nebulas Rank :, IPFS, Genaro[27][28], Core Nebulas Rank. Core Nebulas Rank, Core Nebulas Rank., TPS. Core Nebulas Rank. Core Nebulas Rank Core Nebulas Rank., Core Nebulas Rank Core Nebulas Rank., Core Nebulas Rank.,, Core Nebulas Rank, Core Nebulas Rank. Core Nebulas Rank, Core Nebulas Rank. Core Nebulas Rank Core Nebulas Rank Core Nebulas Rank, Core Nebulas Rank,. Core Nebulas Rank., Nebulas Force Core Nebulas Rank., Core Nebulas Rank (LLVM IR ). Nebulas (NVM), Core Nebulas Rank Core Nebulas Rank.,. 19

22 7 Extended Nebulas Rank Core Nebulas Rank. Core Nebulas PoD( ) DIP( ), Core Nebulas Rank.,, Extended Nebulas Rank. Extended Nebulas Rank Core Nebulas Rank Nebulas. 7.1 Extended Nebulas Rank Nebulas. DApp. DApp... (Acyclic Graph), Page Rank Nebulas Rank. 7.2 Extended Nebulas Rank.,. Extendede Nebulas Rank,, Core Nebulas Rank. Extended Nebulas Rank, Core Nebulas Rank.., Extented Nebulas Rank Core Nebulas Rank. Extended Nebulas Rank Extended Nebulas Rank,. Extended Nebulas Rank. 20

23 8 Nebulas Rank.. Nebulas : Nebulas Rank..,., DApp. Dapps.. Nebulas... Nebulas. 21

24 [1] S. Meiklejohn, M. Pomarole, G. Jordan, K. Levchenko, D. McCoy, G. M. Voelker, and S. Savage, A fistful of bitcoins: characterizing payments among men with no names, in Proceedings of the 2013 conference on Internet measurement con- ference, pp , ACM, [2] Http cookie. [3] Nabulas Technical White Paper. NebulasTechnicalWhitepaper.pdf. Accessed: [4] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, [5] Namecoin. [6] Openassets protocol. open-assets-protocol. [7] V. Buterin et al., Ethereum white paper, [8] Forget fintech welcome to the valueweb. 02/forget-fintech-welcome-to-the-valueweb.html/. [9] L. Page, S. Brin, R. Motwani, and T. Winograd, The pagerank citation ranking: Bringing order to the web., tech. rep., Stanford InfoLab, [10] M. Fleder, M. S. Kester, and S. Pillai, Bitcoin transaction graph analysis, arxiv preprint arxiv: , [11] Q. Li, T. Zhou, L. Lu, and D. Chen, Identifying influential spreaders by weighted LeaderRank, Physica A: Statistical Mechanics and its Applications, vol. 404, pp , [12] A. Cheng and E. Friedman, Manipulability of pagerank under sybil strategies, [13] NEM Technical Reference. Accessed: [14] A. N. Nikolakopoulos and J. D. Garofalakis, NCDawareRank, Proceedings of the sixth ACM international conference on Web search and data mining - WSDM 13, no. February 2013, p. 143, [15] X. Xu, N. Yuruk, Z. Feng, and T. A. Schweiger, Scan: a structural clustering algorithm for networks, in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp , ACM, [16] H. Shiokawa, Y. Fujiwara, and M. Onizuka, Scan++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs, Proceedings of the VLDB Endowment, 22

25 vol. 8, no. 11, pp , [17] L. Chang, W. Li, L. Qin, W. Zhang, and S. Yang, pscan: Fast and exact structural graph clustering, IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 2, pp , [18] J. Hopcroft and D. Sheldon, Manipulation-resistant reputations using hitting time, in International Workshop on Algorithms and Models for the Web-Graph, pp , Springer, [19] J. Zhang, R. Zhang, J. Sun, Y. Zhang, and C. Zhang, Truetop: A sybil-resilient system for user influence measurement on twitter, IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp , [20] A. Cheng and E. Friedman, Sybilproof reputation mechanisms, in Proceed- ings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pp , ACM, [21] M. Swan, Blockchain: Blueprint for a new economy. O Reilly Media, Inc., [22] R. S. Kroszner, Liquidity and monetary policy, [23] R. Selden, Monetary velocity in the united states, [24] CoinMarketCap. [25] D. Quercia and S. Hailes, Sybil attacks against mobile users: friends and foes to the rescue, in INFOCOM, 2010 Proceedings IEEE, pp. 1 5, IEEE, [26] Wikipedia contributors, Sybil attack Wikipedia, the free encyclopedia, [Online; accessed 25-June-2018]. [27] Ipfs. [28] Genaro. 23

26 !!!! A. A.1 Proof of Property 1 proof x 1 > 0,x 2 > 0!. For any!, we have f (x 1 + x 2 ) = = = x 1 + x e a+ b (x 1+ x 2 ) x e + x 2 a+ b (x 1+ x 2 ) 1 + e a+ b (x 1+ x 2 ) x e b x 2 e a+ b x 1 + x e b x 1 e a+ b x 2 b < 0 0 < e (a+ b) x 1 < 1,0 < e b x 2< 1, In formula 21, we have!, so! moreover, x e b x 2 e a+ b x 1 > x e a+ b x 1 = f (x 1 ) x e b x 1 e a+ b x 2 > x e a+ b x 2 = f (x 2 ) is actually: f (x 1 + x 2 ) > f (x 1 ) + f (x 2 ) A.2 Proof of Property 2 proof x 1 > 0,x 2 > 0!. For any!, we have f (x 1 + x 2 ) f (x 1 ) f (x 2 ) = x 1 + x e x 1 x 2 a+ b (x 1+ x 2 ) 1 + e a+ b x e a+ b x 2 x 1 x 1! (23) = ( ) 1 + e b x 2 e a+ b x e a+ b x 1 x 2 x 2 + ( ) 1 + e b x 1 e a+ b x e a+ b x 2 g (x 1, x 2 ) h (x 1, x 2 ) Here we use function! represents the left part,! represents the right part: x 1 x 1! (24) g (x 1, x 2 ) = 1 + e b x 2 e a+ b x e a+ b x 1

27 !!!! x 2 x 2! (25) h (x 1, x 2 ) = 1 + e b x 1 e a+ b x e a+ b x 2 x 1 x 2 So (23) for! and!, their limits can be represented as: lim x 1,x 2 we have [ f (x 1 + x 2 ) f (x 1 ) f (x 2 )] = lim g (x 1, x 2 ) + x 1,x 2 lim h (x 1, x 2 ) x 1,x 2 g (x 1, x 2 ) = = < < x 1 x e b x 2 e a+ b x e a+ b x 1 x 1 e a+ b x 1 (1 e b x 2) (1 + e b x 2 e a+ b x 1) (1 + e a+ b x 1) x 1 e a+ b x 1 (1 + e a+ b x 1) (1 + e b x 2 e a+ b x 1) (1 + e a+ b x 1) = x 1 e a+ b x1 1 + e b x 2 e a+ b x 1 x 1 e a+ b x e a+ b x 1 = 1 + x 1 1 e a+ b x 1 x Calculate limit for!, according to L Hospital s rule, ea+ b x lim x 1 + x 1 = lim 1 x (e a b x ) e a+ b x = lim x 1 b e a b x b < 0 lim b e a b x = In formula 21, we have!, so!, moreover, x lim x 1 + x = 0 1 e a+ b x g (x 1, x 2 ) > 0, According to A.1, we have! so according to sandwich theorem: 25

28 !!! lim x 1,x 2 g (x 1, x 2 ) = 0 Similarly, we can get: lim x 1,x 2 h (x 1, x 2 ) = 0 So, lim x 1,x 2 [ f (x 1 + x 2 ) f (x 1 ) f (x 2 )] = 0 26

29 B. v1.0 v v

위해 사용된 기법에 대해 소개하고자 한다. 시각화와 자료구조를 동시에 활용하는 프로그램이 가지는 한계와 이를 극복하기 위한 시도들을 살펴봄으로서 소셜네트워크의 분석을 위한 접근 방안을 고찰해 보고자 한다. 2장에서는 실험에 사용된 인터넷 커뮤니티인 MLBPark 게시판

위해 사용된 기법에 대해 소개하고자 한다. 시각화와 자료구조를 동시에 활용하는 프로그램이 가지는 한계와 이를 극복하기 위한 시도들을 살펴봄으로서 소셜네트워크의 분석을 위한 접근 방안을 고찰해 보고자 한다. 2장에서는 실험에 사용된 인터넷 커뮤니티인 MLBPark 게시판 인터넷 커뮤니티 사용자의 사회 연결망 특성 분석 Analysis Social Network Characteristics Among the Internet Community Users 탁해성 부산대학교 컴퓨터공학과 tok33@pusan.ac.kr Abstract 인터넷이 사람들에게 보급됨에 따라 온라인 환경에서 소통을 하는 사람들이 늘어났다. 온라인 커뮤니티가